Merge sort

Divide and conquer, a recursive merge sort, why it is O(n log n) in every case, and its O(n) memory cost.

A5.5Algorithms and complexityA level25 min

At GCSE (F5.9) you split a list into ones and merged them back together, and saw merge sort beat bubble sort on a big list. At A level you write merge sort recursively, trace it, and show why it is O(n log n) in every case, and what it costs in memory.

Divide and conquer

Merge sort is a divide and conquer algorithm (module A2): it splits the problem into smaller problems of the same kind, solves those, and combines the answers.

1. Divide: split the list into two halves.
2. Conquer: merge sort each half. A list of 0 or 1 items is already sorted: that is the base case.
3. Combine: merge the two sorted halves into one sorted list.

All the real work is in step 3. Merging two sorted lists only ever compares their two front items, takes the smaller, and moves on. When one list runs out, the rest of the other is copied across with no more comparisons.

A trace

Sorting [52, 17, 83, 30, 9, 64, 41, 25]. The splits go down, the merges come back up, and the number in brackets is the comparisons that merge made:

split   [52, 17, 83, 30, 9, 64, 41, 25]
        [52, 17, 83, 30]         [9, 64, 41, 25]
        [52, 17]   [83, 30]      [9, 64]   [41, 25]
        [52] [17]  [83] [30]     [9] [64]  [41] [25]
merge   [17, 52]   [30, 83]      [9, 64]   [25, 41]      (1 each)
        [17, 30, 52, 83]         [9, 25, 41, 64]         (3 each)
        [9, 17, 25, 30, 41, 52, 64, 83]                  (7)

Total: 4 × 1 + 2 × 3 + 7 = 17 comparisons for 8 items.

In pseudocode

In pseudo-code in AQA's style (AQA's notation has no standard way to slice or extend a list, so here items[a:b] means the items from index a up to, but not including, b, and APPEND adds an item to the end of a list):

SUBROUTINE MergeSort(items)
    IF LEN(items) <= 1 THEN
        RETURN items
    ENDIF
    mid ← LEN(items) DIV 2
    left ← MergeSort(items[0:mid])
    right ← MergeSort(items[mid:LEN(items)])
    RETURN Merge(left, right)
ENDSUBROUTINE

SUBROUTINE Merge(left, right)
    result ← []
    i ← 0
    j ← 0
    WHILE i < LEN(left) AND j < LEN(right)
        IF left[i] <= right[j] THEN
            APPEND left[i] TO result
            i ← i + 1
        ELSE
            APPEND right[j] TO result
            j ← j + 1
        ENDIF
    ENDWHILE
    WHILE i < LEN(left)
        APPEND left[i] TO result
        i ← i + 1
    ENDWHILE
    WHILE j < LEN(right)
        APPEND right[j] TO result
        j ← j + 1
    ENDWHILE
    RETURN result
ENDSUBROUTINE

The same in Python, counting comparisons:

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

def merge_sort(items):
    if len(items) <= 1:
        return items, 0
    mid = len(items) // 2
    left, a = merge_sort(items[:mid])
    right, b = merge_sort(items[mid:])
    merged, c = merge(left, right)
    return merged, a + b + c

print(merge_sort([52, 17, 83, 30, 9, 64, 41, 25]))
for n in [8, 64, 1024]:
    print(n, "items: sorted", merge_sort(list(range(n)))[1], "comparisons, reversed",
          merge_sort(list(range(n, 0, -1)))[1])

Run this in the simulator

Why it is O(n log n)

Think of the trace as levels.

• How many levels? Each split halves the pieces, so going from n items down to pieces of 1 takes log₂ n levels of splitting (3 levels for 8 items), and the same number of levels of merging.
• How much work per level? On any one level, the merges between them handle every one of the n items once. Merging a total of m items takes at most m - 1 comparisons, so each level costs at most about n.

Levels × work per level = log₂ n × n, so merge sort is O(n log n).

Crucially, this does not depend on the data. A sorted list still gets split all the way down and merged all the way up. Merging two halves takes at least as many comparisons as the shorter half has items, so even the luckiest data needs at least half the worst-case work. The best, average and worst cases are all O(n log n).

At 8 items there is no real difference. At a million items bubble sort needs about 25,000 times as many comparisons as merge sort.

The cost: memory

Merge sort is not in place. Each merge builds a new list, and the final merge needs room for all n items alongside the halves it is merging, so it needs O(n) extra space. The recursion also holds up to log₂ n calls on the stack at once, but O(n) is the bigger term. On a robot with little RAM and a big array, that can rule merge sort out.

Merge sort is stable as long as the merge takes from the left list when the two front items are equal (the <=), so equal items keep their order. That, and its guaranteed O(n log n), is why merge sort is used for sorting records and for sorting files too big for memory: the halves can be sorted separately and merged from disk.

Task: merge sort the readings

Write merge_sort(items) recursively (it must call itself; do not use sort or sorted). It takes a list of numbers and returns a tuple (sorted_list, comparisons): a new list in ascending order, and the number of times two items were compared while merging. Compare with <= so the sort is stable; copying the leftovers at the end of a merge is not a comparison.

Print exactly three lines:

• sorted: followed by the readings in ascending order
• readings: <n> comparisons, for sorting readings
• ordered: <n> comparisons, for sorting ordered, which is already in order

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

readings = [57, 16, 34, 26, 51, 15, 31, 35, 26, 34, 16, 31, 48, 22, 40, 9]
ordered = list(range(1, 17))

def merge_sort(items):
    return items, 0

Challenges

1. What is the largest number of comparisons merge sort can make on 16 items? Build a list that needs exactly that many.
2. Write merge sort without recursion: merge pieces of size 1 into 2, then 2 into 4, and so on.
3. Sort a list of (name, time) records by time with your merge sort. Check that two runs with equal times stay in their original order.