Merge sort: two sorted halves make a sorted whole

A teacher has 600 exam papers to put in order of surname. Slotting them one at a time into a growing sorted pile, as insertion sort does, means checking each new paper against papers already placed: the O(n²) pattern of the simple sorts in sorting in code. So she hands half the stack to a colleague. Each sorts 300, and the two sorted piles go face up on the desk. The first paper overall must be on top of one pile or the other, so she takes the earlier of the two top papers, again and again, until both piles are gone. Merging is easy because both piles are already sorted.

Merge sort does that all the way down: halves of halves, until every pile holds one paper, which is sorted by definition. For a million items, that turns insertion sort's worst case of about 500 billion comparisons into about 20 million.

divide and conquer

Split a problem into smaller copies of itself, solve each, and combine the answers.

run

A stretch of values already in sorted order. A single value is a run, and each merge turns two runs into one.

merge

Combining two sorted runs into one by repeatedly comparing their front values and taking the smaller.

buffer

Extra space the merge writes into, here a second row B as long as the array, before the merged run is copied back.

stable

A sort is stable if equal values keep the order they started in. It matters when you sort records by one field.

Here are 8 values. Play the run, and watch where the comparisons happen.

Splitting is only arithmetic: mid = ⌊(lo + hi) / 2⌋, with no comparisons and no moves. It stops at pieces of one value, because one value is already sorted. The calls run depth first, as in the recursion lesson, so the left half is completely sorted before the right half is even split.

All the work is in the merges. Both halves are sorted, so the smallest value left must be at the front of one of them: compare the two fronts, move the smaller into the buffer, and step that side on. Each comparison places one value, and once one half runs out, the rest of the other follows with no comparisons at all.

Now count by level. The pieces on one level hold all n values between them, and each value is placed with at most one comparison, so a level costs fewer than n comparisons: above, the levels cost 4, 6 and 7 for 8 values. Halving 8 values reaches pieces of one after 3 levels, and halving a million takes 20, because 2²⁰ is just over a million.

For a million values that is about 20 million comparisons, against n²/2, or 500 billion, for insertion sort on a reversed list: at a billion a second, a fiftieth of a second against more than eight minutes. Here are both sorts on reversed lists, insertion sort's worst order:

At n = 64 insertion sort makes about 2,000 comparisons and merge sort about 200. Doubling n from 32 multiplies insertion sort's count by about 4, the mark of O(n²), and merge sort's by about 2.4.

Before each merge step, predict which value goes into the buffer. Look only at the two front values: the smaller goes in. This list has two pairs of equal values. When the fronts tie, read the merge line in the code panel, A[i] ≤ A[j]: it takes the left one.

Here is the merge on its own, on two short sorted lists, with one index walking each, as in two pointers. When one list runs out, the other's leftovers are copied across.

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

merged = merge([4, 7, 12], [3, 7, 9, 15])
print(*merged)

That is the hard part. The sort around it is a few lines of recursion: stop at one value, find mid, sort each half, merge.

Does the order of the input help? Here is a list that is already sorted.

That is about as few as merge sort ever makes: it still splits all the way down and merges every level, and Writes stays at 128, as on any 16 values. Switch the input to Reversed or Random and Comparisons ends at 33 or 45. Insertion sort makes just 15 on the sorted list. So insertion sort ranges from n − 1 comparisons to about n²/2, while merge sort stays between about ½ n log₂ n and n log₂ n.

Real libraries take the best of both. Python's sorted and list.sort, Java's sort for objects and JavaScript's Array.prototype.sort in V8 (Chrome and Node) all use Timsort or a close relative: a merge sort that first finds runs already in order, lengthens short ones with insertion sort, then merges the runs. A sorted list is one run, so it finishes in n − 1 comparisons, and the worst case is still O(n log n).

The visualiser draws a second row under the array, the merge buffer B. In the first run, on 8 values, Writes ended at 48: each of the 3 levels moved all 8 values into B and back again.

One character in the merge decides something else: the ≤ in A[i] ≤ A[j].

• Merge sort halves the array until each piece holds one value, then merges sorted pieces back together. Splitting compares nothing; all the work is in the merges.
• A merge compares two front values and takes the smaller, so each comparison places one value: at most a + b − 1.
• About log₂ n levels at fewer than n comparisons each make O(n log n) on every input: about 20 million comparisons for a million values, not 500 billion.
• It needs a buffer as long as the array, so it isn't in place, and taking the left value on ties makes it stable.
• Sorted input still costs merge sort about ½ n log₂ n comparisons, while insertion sort's drop to n − 1. Timsort, in Python, Java and V8, merges the runs it finds to get both.
• Next: quick sort, which divides around a pivot and sorts in place, intervals, where sorting by start comes first, and storage engines, where compaction merges sorted runs on disk. Practise with Merge Two Sorted Linked Lists and Merge Overlapping Intervals, or open the merge sort visualiser and race the sorts.