Merge Sort — The Atlas of Algorithms

What you're seeing

Each bar is a number; taller is larger. Merge sort (shown here bottom-up) starts by treating every element as a sorted run of length one, then merges adjacent runs into runs of width 2, then 4, then 8 — doubling each pass until one run spans everything. The animation zooms in on one merge at a time: two already-sorted runs (blue and purple) feed a single sorted output (green) by repeatedly taking whichever run's front value is smaller.

Notice that every frame is a valid arrangement of the original values — the green output and the two shrinking run-tails always account for the whole segment.

The rule

merge_sort(a):                 # bottom-up
    for width = 1, 2, 4, … < n:
        for lo = 0, 2·width, … < n:
            merge a[lo .. lo+width) and a[lo+width .. lo+2·width)

merge(left, right):            # two sorted runs → one sorted run
    while both nonempty:
        take the smaller front value
    append whatever remains

The merge is the heart of it: a single linear pass over two sorted runs produces one sorted run, taking (len left + len right) − 1 comparisons at most.

The invariant

Two invariants stack. The merge keeps one: as it runs, the output built so far is sorted, and holds exactly the values already consumed from the two runs — and because both runs are sorted, the smaller of their two fronts is the smallest value not yet placed, so appending it keeps the output sorted. The outer loop keeps the other: after the pass for a given width, every aligned block of that width is a sorted run. Merging two sorted runs (the merge invariant) extends this to double the width; once the width reaches n, the single block — the whole array — is sorted. Sorted sub-runs combine into sorted super-runs, all the way up.

The cost

BestAverageWorst ComparisonsΘ(n log n)Θ(n log n)Θ(n log n) TimeΘ(n log n)Θ(n log n)Θ(n log n) SpaceO(n)O(n)O(n)

There are ⌈log₂ n⌉ passes; each pass merges all n elements in linear time — so Θ(n log n) comparisons in every case, the first guarantee in this atlas that holds regardless of input. Try Reversed versus Random: the comparison counter barely moves. The price is O(n) auxiliary space for the merge — merge sort is the classic time-for-space trade against the in-place quadratic sorts. And it is stable: ties are broken toward the left run (left[i] ≤ right[j] takes the left), so equal keys keep their original order.

In the wild

Merge sort is everywhere stability and guaranteed performance matter. Timsort — Python's sorted(), Java's Arrays.sort() for objects, the Android and V8 runtimes — is an adaptive, natural merge sort: it finds existing sorted runs in the data and merges them, using insertion sort to extend short runs. Merge sort is also the backbone of external sorting: when data is too large for RAM, databases and sort(1) sort chunks that fit in memory and then merge the sorted chunks streaming from disk — the merge step needs only sequential reads, which is exactly what disks and SSDs are fast at. Its divide-and-conquer shape also parallelizes cleanly.

Try this

Step through a single merge with the ▶| button and watch the green output grow one bar at a time as the blue and purple run-tails shrink — each bar taken is the smaller of the two current fronts. Then switch between Random and Reversed and confirm the comparison count hardly changes: merge sort doesn't care how the data started.

References

Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §2.3 — merge sort, the merge procedure, and its loop invariant; the Θ(n log n) recurrence. MIT Press, 2022.
Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching, §5.2.4 (Sorting by Merging) — including external/tape merging. Addison-Wesley.
Peters, T. Timsort design notes (adaptive natural merge sort), CPython listsort.txt: github.com/python/cpython · Objects/listsort.txt.
Sedgewick & Wayne. Algorithms, 4th ed., §2.2 (Mergesort) — top-down and bottom-up, stability, O(n) space. algs4.cs.princeton.edu/22mergesort.