Recursive Merge Sort

various: Up to 15 points

Objective

Just as you did with Insertion, Selection and Bubble sort, adapt the code below to add a visualization for Merge Sort.

Merge Sort

def merge(left, right):
    i,j = 0,0
    result = []
    while i < len(left) and j < len(right):
    if left[i] < right[j]:
        result.append(left[i])
        i += 1
    else:
        result.append(right[j])
        j += 1
    result += left[i:]
    result += right[j:]
    return result


def merge_sort(values):
    if len(values) <= 1:
        return values 
    halfway = len(values) // 2
    left = merge_sort(items[:halfway])
    right = merge_sort(items[halfway:])
    return merge(left, right)

Requirements

  • You must define a merge_sort_demo function. Like the other functions already in sorts.py, it should:
    • Accept a single argument, which must be either a DataSet or a VisualDataSet object.
    • Perform a recursive Merge Sort on the object and call its display method whenever one a value is assigned to a new position.
    • Include an appropriate docstring.
  • Follow all the same steps you used to add your Bubble Sort demo. Namely:
    1. Define the new algorithm in sorts.py (using any helper functions you need).
    2. Add a test for the new demo to the body of sorts.py (see the Testing section below for more details).
    3. Update the menu and code in main.py to make your Merge Sort demo available as an option to the user.
  • You will need to modify the code given above to get your visualization to work. However, your solution must remain recursive to earn credit for this task.

Testing

Just as with the other sorts, add code in the main body of sorts.py to set the values of your test_data object back to [8, 6, 4, 2, 0, 1, 3, 5, 7, 9] and call the demo_test on your new sort. Inspect the resulting text-based visualization to make sure it’s behaving the way you expect. Use the provided list of values, the relevant terminal output should be:

*******************************************************************************
Testing merge_sort_demo
-------------------------------------------------------------------------------
Initial data values:
[8, 6, 4, 2, 0, 1, 3, 5, 7, 9]
Sorted: False
Running demo...
6	6	4	2	0	1	3	5	7	9	

6	8	4	2	0	1	3	5	7	9	

6	8	4	0	0	1	3	5	7	9	

6	8	4	0	2	1	3	5	7	9	

6	8	0	0	2	1	3	5	7	9	

6	8	0	2	2	1	3	5	7	9	

6	8	0	2	4	1	3	5	7	9	

0	8	0	2	4	1	3	5	7	9	

0	2	0	2	4	1	3	5	7	9	

0	2	4	2	4	1	3	5	7	9	

0	2	4	6	4	1	3	5	7	9	

0	2	4	6	8	1	3	5	7	9	

0	2	4	6	8	1	3	5	7	9	

0	2	4	6	8	1	3	5	7	9	

0	2	4	6	8	1	3	5	7	9	

0	2	4	6	8	1	3	5	7	9	

0	2	4	6	8	1	3	5	7	9	

0	2	4	6	8	1	3	5	7	9	

0	2	4	6	8	1	3	5	7	9	

0	2	4	6	8	1	3	5	7	9	

0	2	4	6	8	1	3	5	7	9	

0	2	4	6	8	1	3	5	7	9	

0	2	4	6	8	1	3	5	7	9	

0	2	4	6	8	1	3	5	7	9	

0	2	4	6	8	1	3	5	7	9	

0	1	4	6	8	1	3	5	7	9	

0	1	2	6	8	1	3	5	7	9	

0	1	2	3	8	1	3	5	7	9	

0	1	2	3	4	1	3	5	7	9	

0	1	2	3	4	5	3	5	7	9	

0	1	2	3	4	5	6	5	7	9	

0	1	2	3	4	5	6	7	7	9	

0	1	2	3	4	5	6	7	8	9	

0	1	2	3	4	5	6	7	8	9	

Demo complete.
Sorted: True

Note that your output could vary slightly depending on the placement of your calls to display.

Hint 1: Sorting in Place

  • The three sorting algorithms you have used so far in this lab have been designed to sort a list in place. This strategy makes it possible to visualize the sort by displaying the list’s values every time it changes.
  • The version of Merge Sort given above is different. Instead of sorting a list in place, it repeatedly replaces lists with new lists until it finally returns a sorted copy of the original. This approach keeps the algorithm simple and easy to read, but makes visualization more challenging.
  • One way to solve this problem is to modify your Merge Sort so the original list is always updated whenever any items are re-ordered. In this approach, any rearrangements that happen during the merge process always get written back to the appropriate place in the original list, which can then be displayed after each change as it is in the other sorting visualizations.

Hint 2: Using a wrapper function

  • Your sorting demo functions all expect to be given a single argument, which is either a DataSet or a VisualDataSet object.
  • However, your recursive Merge Sort function might need to take more than one argument. For example, you might want it to accept a DataSet / VisualDataSet along with some other values that help you perform your in-place sort.
  • To resolve this discrepancy, you can use merge_sort_demo as a wrapper function for your recursive Merge Sort. What this means is that the only purpose of merge_sort_demo is to figure out the correct initial values that you need to start your recursive sorting function, and then execute it with these parameters.
  • For example, say your recursive Merge Sort function is called merge_sort(param1, param2, param3). In this case, the code for your merge_sort_demo might look something like this:
    def merge_sort_demo(data):
    # TODO: Code here to calculate param1
    # TODO: Code here to calculate param2
    # TODO: Code here to calculate param3
    merge_sort(param1, param2, param3)
    return
  • If you take this approach, you would end up writing three functions altogether: merge, merge_sort and merge_sort_demo.