CS 115 Lab 11, Part C: Mergesort

[Back to lab instructions]


Instructions

  1. Make a new copy of your lab11b.py. Name it lab11c.py.
  2. In main, comment out all of your code for now..
  3. Add the following function definition to your code:
    def merge(L, start_index, sublist_size):
        """
        Merge two sublists of a list L
    
        Parameters:
        L - the list
        start_index - the index of the first element to be merged
        sublist_size - the size of the chunks to be merged
    
        Left chunk: L[start_index] to L[start_index + sublist_size - 1]
        Right chunk: L[start_index + sublist_size] to L[start_index + 2 * sublist_size - 1]
        """
    
        index_left = start_index
        left_stop_index = start_index + sublist_size
        index_right = start_index + sublist_size
        right_stop_index = min(start_index + 2 * sublist_size,
                               len(L))
    
        print('Merging sublists:', L[index_left:left_stop_index], 'and',
              L[index_right:right_stop_index]);
    
        L_tmp = []
    
        while (index_left < left_stop_index and
               index_right < right_stop_index):
            if L[index_left] < L[index_right]:
               L_tmp.append(L[index_left])
               index_left += 1
            else:
               L_tmp.append(L[index_right])
               index_right += 1
    
        if index_left < left_stop_index:
               L_tmp.extend(L[index_left : left_stop_index])
        if index_right < right_stop_index:
               L_tmp.extend(L[index_right : right_stop_index])
    
        L[start_index : right_stop_index] = L_tmp
        print('Merged sublist:', L_tmp, '\n')
    
  4. In main, add the following call to merge at the end:
    merge(['Healdsburg', 'Windsor', 'Rohnert Park', 'Santa Rosa'], 0, 2)

    This code will do the following to the 4-element list that we passed to it:

  5. Answer Questions 8 and 9 in your writeup.
  6. Now, we'll use this code to help us sort an entire list. Here's how: Here is some code that does the first step:
    def merge_sort(L):
        """
        Sort a list L using the merge sort algorithm.
    
        (Starter code doesn't fully sort the list.)
        """
        chunksize = 1  # Start by dividing the list into N sub-lists of 1 element each
    
        print("\n*** Sorting sublists of size", chunksize)
    
        # Divide the list into pairs of chunks
        left_start_index = 0  # Start of left chunk in each pair
    
        # While we still have chunks to merge
        while left_start_index + chunksize < len(L):
            merge(L, left_start_index, chunksize)
    
            # Move to next pair of chunks
            left_start_index += 2 * chunksize
    
        print('List is now', L)
    
  7. In main, remove your call to merge, and put the rest of your code back in. Comment out the call to selection sort, and call merge_sort instead for now.
  8. To continue sorting the list, modify your code as follows: Sample input/output:
    Name of input file: cities-small.txt
    
    The original list of cities is:
    0: Santa Rosa
    1: Petaluma
    2: Rohnert Park
    3: Windsor
    4: Healdsburg
    
    *** Sorting sublists of size 1
    Merging sublists: ['Santa Rosa'] and ['Petaluma']
    Merged sublist: ['Petaluma', 'Santa Rosa'] 
    
    Merging sublists: ['Rohnert Park'] and ['Windsor']
    Merged sublist: ['Rohnert Park', 'Windsor'] 
    
    List is now ['Petaluma', 'Santa Rosa', 'Rohnert Park', 'Windsor', 'Healdsburg']
    
    *** Sorting sublists of size 2
    Merging sublists: ['Petaluma', 'Santa Rosa'] and ['Rohnert Park', 'Windsor']
    Merged sublist: ['Petaluma', 'Rohnert Park', 'Santa Rosa', 'Windsor'] 
    
    List is now ['Petaluma', 'Rohnert Park', 'Santa Rosa', 'Windsor', 'Healdsburg']
    
    *** Sorting sublists of size 4
    Merging sublists: ['Petaluma', 'Rohnert Park', 'Santa Rosa', 'Windsor'] and ['Healdsburg']
    Merged sublist: ['Healdsburg', 'Petaluma', 'Rohnert Park', 'Santa Rosa', 'Windsor'] 
    
    List is now ['Healdsburg', 'Petaluma', 'Rohnert Park', 'Santa Rosa', 'Windsor']
    
    The new list of cities is:
    0: Healdsburg
    1: Petaluma
    2: Rohnert Park
    3: Santa Rosa
    4: Windsor
  9. Test your code on the larger cities.txt file, and answer Questions 10 and 11 in your writeup.
  10. Add code to main that lets the user select whether to sort using selection sort or merge sort. You can assume that the user's input will always be 's', 'S', 'm', or 'M':
    Name of input file: cities-small.txt
    Type S for selection sort and M for merge sort: m
    
    The original list of cities is:
    0: Santa Rosa
    1: Petaluma
    2: Rohnert Park
    3: Windsor
    4: Healdsburg
    ...etc.
    
  11. Demo your program.
  12. Continue to Part D.