Back to Lesson 27

Exercise: Running time of merge sort

Recall that merge sort requires first dividing the list into halves, then sorting the two halves (recursvely, using merge sort), and finally merging the two sorted sublists back together. Here is the code for merge sort:

def mergeSort(mylist):
    n = len(mylist)

    # If the list contains 0 or 1 item, we have no work to do
    if n < 2:
        return

    # First, divide the list into two smaller lists
    mid = n // 2
    left, right = mylist[:mid], mylist[mid:]

    # Next, recursively sort each sublist
    mergeSort(left)
    mergeSort(right)

    # Finally, merge the two sorted sublists back together
    merge(left, right, mylist)

Part a: Predicting running times

Recall that we said that merge sort does an amount of work roughly equal to n * log_2(n). Using that information, fill in the following table.

Part b: Plotting running times

Download this sorting program and run it to graph how long it takes to sort a random list, on average, using both selection sort and merge sort.

Note that with num_trials=1000 data points per value of n and with the given list of values of n, it might take at least five minutes to run. You can decrease num_trials to make it run faster, although then it won’t test with as much data.

Back to Lesson 27