Back to Lesson 27

Exercise: Running time of merge sort

Recall that merge sort requires first dividing, sorting the two halves (recursvely, using merge sort), and then 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
    m = n // 2
    left, right = mylist[:m], mylist[m:]

    # 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 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 numTests to make it run faster, although then it won’t test with as much data.

Back to Lesson 27