Python Arena
Start learning
Step 2 of 6

Merge sort

Insertion sort is O(n²) on most lists: for 200,000 values in a random order, about 10 billion moves, far too slow in Python. Merge sort does the same job in O(n log n). Its idea is called divide and conquer: split the problem into halves, solve each half in the same way, and combine the two answers into one.

Merging two sorted lists

The combining step is a merge: two lists that are each sorted become one sorted list. The smallest item of all is at the front of one of the two lists, so compare the two front items, take the smaller one, and step past it. Two indexes, i and j, remember where the front of each list is now:

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


print(merge([2, 5, 8, 13], [1, 5, 6, 17, 30]))
Output
[1, 2, 5, 5, 6, 8, 13, 17, 30]

Each round of the loop takes one item, so a merge costs O(len(left) + len(right)). The loop stops as soon as one list runs out, and the other one may still have items, all at least as big as everything taken so far. The last two lines add them. Forget them, and this merge returns [1, 2, 5, 5, 6, 8, 13]: no error, just 17 and 30 quietly gone.

Two more details matter. On a tie, <= takes the item from the left list first, so equal items keep their order: merge sort is stable. And don't take the front item with left.pop(0). Removing the first item of a list moves all the others one place, which is O(n) each time; the indexes keep each step O(1).

Splitting and merging

Now merge sort itself. A list of 0 or 1 items is already sorted: that's the base case. Any longer list is split in the middle, each half is sorted by a call of merge_sort, and the two sorted halves are merged:

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


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


print(merge_sort([9, 4, 7, 1, 6, 3, 8]))
Output
[1, 3, 4, 6, 7, 8, 9]

Here is what happens inside, level by level. Seven items don't halve evenly, so the left half gets 3 and the right half 4:

[9, 4, 7, 1, 6, 3, 8]
[9, 4, 7]           [1, 6, 3, 8]            split
[9]   [4, 7]        [1, 6]     [3, 8]       split
[9]   [4]  [7]      [1]  [6]   [3]  [8]     single items are sorted
[9]   [4, 7]        [1, 6]     [3, 8]       merge
[4, 7, 9]           [1, 3, 6, 8]            merge
[1, 3, 4, 6, 7, 8, 9]                       merge

Why is it right? A list of 0 or 1 items is sorted. A longer list splits into two shorter ones, so the calls get smaller and end; and when both halves come back sorted, merging them gives a sorted list.

What it costs

  • Time. Halving 200,000 values again and again gets down to single items after 18 levels: about log n levels (log to the base 2). At each level, the merges together take each of the n values once, so each level is O(n). In all, O(n log n): about 3.6 million steps for 200,000 values, where insertion sort needs billions. That holds in the worst case too: no input slows merge sort down.
  • Memory. The slices values[:middle] and values[middle:] are copies, and each merge builds a new list, so merge sort needs O(n) extra memory. Insertion sort needs none.
  • Recursion depth. The calls only go about log n deep, 18 levels for 200,000 values, so Python's limit of about 1,000 nested calls is never near.

Your task

Challenge 1 of 3

This merge sort prints every list it merges. What does the program print? Type each line it prints.

Challenge 2

A quiz app shows its results from the highest score to the lowest, and players with the same score in the order they finished, which is their order in the list. Write rank_results(results) with merge sort, where results is a list of (name, score) tuples. It returns a new list sorted by score from the highest to the lowest, with equal scores kept in their original order. It must be fast for 80,000 results. Don't use sorted or sort.

For example, this program:

results = [("Ada", 7), ("Bo", 9), ("Cy", 7), ("Di", 10)]
for name, score in rank_results(results):
    print(name, score)

prints:

Di 10
Bo 9
Ada 7
Cy 7

Challenge 3

An inversion is a pair of items in the wrong order: a bigger item before a smaller one. [4, 6, 2, 5] has 3 of them: 4 and 2, 6 and 2, 6 and 5. It's the number of moves insertion sort makes, a measure of how far a list is from sorted. Write count_inversions(values), which returns the number of inversions of a list. It must be fast for 60,000 values, so count them while you merge sort, in O(n log n).

The trick is in the merge. When the front item of the right half is smaller than the front item of the left half, it's smaller than every item still waiting in the left half (that half is sorted), and all of those came before it in the list. So taking it counts len(left) - i inversions at once. The inversions inside each half are counted by the calls that sort the halves.

For example, count_inversions([4, 6, 2, 5]) returns:

3
Previous: Insertion sort Next: Quicksort and partitioning