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:

   • Starting at index 0 (the second parameter), look at a pair of adjacent 2-element chunks (the 2 comes from the third parameter).
   • Assuming that each of the individual chunks is in sorted order, merge them into a single, sorted 4-element chunk.
5. Answer Questions 5 and 6 in your writeup.
6. Now, we'll use this code to help us sort an entire list. Here's how:
   • Start by merging pairs of adjacent elements (1-element chunks). Now we will have a bunch of adjacent 2-element sorted lists.
   • Merge pairs of adjacent 2-element chunks. Now we will have a bunch of adjacent 4-element sorted lists.
   • Keep doubling the size of the lists to be merged until the entire list is in sorted order.
   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:
   • Move all of this code (except for the initialization statement) into an outer loop. The loop should continue as long as your chunk size is less than the size of the list.
   • At the end of each outer loop iteration, double chunksize.
   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 7 and 8 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.