Merge sort

Why sorting a million songs takes 20 million steps, not a trillion

Merge sort splits a list in half, sorts each half by calling itself (recursion), then merges the two sorted halves into one. A list of one item is already sorted, so that is where the splitting stops.

Take [5, 2, 8, 1]. It splits into [5, 2] and [8, 1], then into single items. Merging back up gives [2, 5] and [1, 8], and merging those gives [1, 2, 5, 8].

Comparing every item with every other takes about n² steps: a trillion for a million songs. Merge sort takes about n · log₂ n, roughly 20 million, since halving a million items reaches single items in about 20 levels.

Merge sort

Python's sorted() and PostgreSQL's big sorts are both built on merging

Python's sorted() uses Timsort, a merge sort that first finds stretches already in order (called runs) and then merges them. Java uses Timsort too when sorting lists of objects.

When a PostgreSQL query sorts more rows than fit in its memory, it sorts chunks that fit, writes each to disk, then merges the sorted chunks. Its query plan then reports the sort method as "external merge".

Merge sort

Merging two sorted piles only ever compares their top cards

Both halves are sorted, so the smallest remaining item is at the front of one of them. Each step compares the two fronts and moves the smaller to the output, so every comparison places one item for good.

Merging [2, 5] and [1, 8]: 1 beats 2, output 1; 2 beats 8, output 2; 5 beats 8, output 5; then 8 is left. Four items placed in three comparisons, never looking back.

Each level of merging costs about n and halving gives log₂ n levels, so the total is n · log₂ n. The price: merging needs a second array as big as the input. Taking from the left on ties keeps equal items in order (stable).