Merge sort

What this chapter covers

Merge sort is the first sort in this book to break the quadratic barrier, and it does so with the divide-and-conquer recursion from two chapters ago: split the array in half, sort each half by recursing, merge the two sorted halves back together. The whole trick is that merging two already-sorted runs takes only linear time, and doing that at every level of the split gives O(n log n) — with no bad case, ever. This chapter builds it, watches the merges assemble longer and longer sorted runs, and races it against the library sort it's the ancestor of.

A bit of history

Merge sort has an unusually precise origin: John von Neumann designed it in 1945, making it one of the very first algorithms written for a stored-program computer. He needed something to demonstrate that the new machines could do more than arithmetic, and sorting by merging — an idea already used by hand with punched cards — was a natural fit for a machine that could shuffle data between memory locations. Nearly eighty years later it's still the backbone of practical sorting: Python's Timsort, Java's Arrays.sort for objects, and essentially every "sort a file too big to fit in memory" routine are merge sorts, because merging is the one sorting operation that works beautifully on sequential data you can only read front to back.

The intuition

Suppose you already had two sorted piles and wanted one sorted pile. You wouldn't re-sort — you'd just repeatedly take the smaller of the two top cards. That's a merge, and it's linear: each card is looked at once. Merge sort is nothing but this observation applied recursively. A single element is already a sorted pile of one. Two sorted piles of one merge into a sorted pile of two; two of those merge into a sorted four; and so on up until the whole array is one sorted pile.

Read top-down, it's divide-and-conquer: to sort an array, sort its left half, sort its right half, and merge. You don't worry about how the halves get sorted — you trust the recursion, exactly the leap from the Hanoi chapter. Read bottom-up, it's the piles doubling in size: runs of 1 merge into runs of 2, then 4, then 8. Both views are the same algorithm, and the animation shows the bottom-up one because the growing runs are the thing to watch.

Complexity: how it scales

Merge sort's cost is the recurrence

— two half-size subproblems plus a linear merge — and it holds in the best, average, and worst case alike, because the split is always exactly in half regardless of the data. That guaranteed $O(n \log n)$ is merge sort's headline feature: quicksort, next chapter, is often faster but has an $O(n^2)$ worst case; merge sort has none. The price is space. The merge needs somewhere to put the combined run, so merge sort uses $O(n)$ extra memory — one auxiliary array — where the in-place sorts use O(1). The chart shows the near-linear growth of $O(n \log n)$ against Timsort:

Both lines are nearly straight — n log n grows only a hair faster than linear over this range, which is why an O(n log n) sort feels essentially free next to the O(n²) sorts of the last chapter.

What it's good at, what it isn't

Merge sort is the sort you reach for when you need guarantees. Its O(n log n) is worst-case, not average, so there's no adversarial input that degrades it — valuable when you can't control the data or an attacker chooses it. It's stable, keeping equal elements in their original order, which matters when you sort by one key and want to preserve a previous ordering. And it only ever reads its input sequentially, which makes it the algorithm for data that doesn't fit in memory (merge sorted chunks from disk) or for linked lists (which have no random access for quicksort to exploit).

Its one real weakness is the O(n) extra memory. For a large in-memory array, that scratch space is a genuine cost, and it's why an in-place sort like quicksort or heapsort is often preferred when worst-case guarantees aren't required. Merge sort trades memory for a guarantee; whether that's a good trade depends on which you have to spare.

The data, or the inputs

The face-off sorts random integer arrays at growing sizes, against Timsort. The animation runs merge sort on twelve elements and records the array after each merge, so you can watch the sorted runs double in length — the bottom-up view of the same recursion.

Build it, one function at a time

The divide half is the recursion: split at the midpoint, sort each side, merge. A run of one element is the base case — already sorted:

def merge_sort(a, probe=None):
    """O(n log n) in every case: recursively sort the two halves, then merge. The
    recurrence is T(n) = 2T(n/2) + O(n) — two half-size sorts plus a linear merge."""
    a = list(a)
    aux = list(a)
    _sort(a, aux, 0, len(a), probe)
    return a


def _sort(a, aux, lo, hi, probe):
    """Sort a[lo:hi] by splitting at the midpoint and recursing on each side. The
    base case — a run of one element — is already sorted, which stops the recursion."""
    if hi - lo <= 1:
        return
    mid = (lo + hi) // 2
    _sort(a, aux, lo, mid, probe)
    _sort(a, aux, mid, hi, probe)
    _merge(a, aux, lo, mid, hi, probe)

The merge is the engine. Copy the two runs aside, then walk them with two fingers, always taking the smaller front element — and taking the left one on ties, which is what makes the sort stable:

def _merge(a, aux, lo, mid, hi, probe=None):
    """Combine two adjacent sorted runs, a[lo:mid] and a[mid:hi], into one sorted
    run in a[lo:hi]. Copy them aside, then walk both with two fingers, always
    taking the smaller front element. This is the linear-time heart of the sort —
    and taking the LEFT element on ties is what makes merge sort stable."""
    aux[lo:hi] = a[lo:hi]
    i, j = lo, mid
    for k in range(lo, hi):
        if i >= mid:                 # left run exhausted — take from the right
            a[k] = aux[j]; j += 1
        elif j >= hi:                # right run exhausted — take from the left
            a[k] = aux[i]; i += 1
        elif aux[i] <= aux[j]:       # tie goes left → stable
            a[k] = aux[i]; i += 1
        else:
            a[k] = aux[j]; j += 1
    if probe is not None:
        probe.append({"arr": list(a), "lo": lo, "hi": hi})

Watch it work

Here's merge sort on twelve bars, shown bottom-up. It starts as twelve sorted runs of length one. Each frame is one merge: two adjacent sorted runs combine into a single longer sorted run, highlighted green. Step through it and watch the green runs grow — length 2, then 4, then 8, then the whole array — which is the log n levels of the recursion playing out. Every element is touched once per level, and there are only log n levels, which is the entire O(n log n) in a picture:

The complete code

Both versions in one place — flip between them. The from-scratch tab is our merge sort with its reusable auxiliary array. The library tab is sorted — Timsort, which is a merge sort that first finds the naturally-sorted runs already in your data and then merges them, using insertion sort to build up the small runs.

"""Merge sort — the first O(n log n) sort, and the cleanest example of
divide-and-conquer. Split the array in half, sort each half by recursing, then
merge the two sorted halves into one. The merge is the clever part: combining two
already-sorted runs takes only linear time, and doing that at every level of the
split is what buys O(n log n) with no bad case.

It's implemented here in the index-based, in-place style real libraries use — one
auxiliary array reused across all the merges — so the animation can watch each
merge produce a longer sorted run.
"""


# region: divide
def merge_sort(a, probe=None):
    """O(n log n) in every case: recursively sort the two halves, then merge. The
    recurrence is T(n) = 2T(n/2) + O(n) — two half-size sorts plus a linear merge."""
    a = list(a)
    aux = list(a)
    _sort(a, aux, 0, len(a), probe)
    return a


def _sort(a, aux, lo, hi, probe):
    """Sort a[lo:hi] by splitting at the midpoint and recursing on each side. The
    base case — a run of one element — is already sorted, which stops the recursion."""
    if hi - lo <= 1:
        return
    mid = (lo + hi) // 2
    _sort(a, aux, lo, mid, probe)
    _sort(a, aux, mid, hi, probe)
    _merge(a, aux, lo, mid, hi, probe)
# endregion


# region: merge
def _merge(a, aux, lo, mid, hi, probe=None):
    """Combine two adjacent sorted runs, a[lo:mid] and a[mid:hi], into one sorted
    run in a[lo:hi]. Copy them aside, then walk both with two fingers, always
    taking the smaller front element. This is the linear-time heart of the sort —
    and taking the LEFT element on ties is what makes merge sort stable."""
    aux[lo:hi] = a[lo:hi]
    i, j = lo, mid
    for k in range(lo, hi):
        if i >= mid:                 # left run exhausted — take from the right
            a[k] = aux[j]; j += 1
        elif j >= hi:                # right run exhausted — take from the left
            a[k] = aux[i]; i += 1
        elif aux[i] <= aux[j]:       # tie goes left → stable
            a[k] = aux[i]; i += 1
        else:
            a[k] = aux[j]; j += 1
    if probe is not None:
        probe.append({"arr": list(a), "lo": lo, "hi": hi})
# endregion

"""Python's `sorted` is Timsort, which is itself a merge sort at heart — it finds
already-sorted runs in the data and merges them (using insertion sort to build up
small runs first). So this face-off is our textbook merge sort against a production
merge sort: same O(n log n), same stability, but Timsort is adaptive (near-linear on
nearly-sorted input) and written in C.
"""


# region: sort_builtin
def sort_builtin(a):
    """Timsort: an adaptive, stable merge sort. O(n log n) worst case, O(n) on
    already-sorted input, implemented in C."""
    return sorted(a)
# endregion

Scratch vs library

Same algorithm class, same stability, so the gap is the usual constant. Sorting 80000 integers took our merge sort about 86 ms against Timsort's 7.5 ms — roughly eleven times slower. Timsort wins on three counts, all constant factors: it's C not Python, it's adaptive (it exploits runs of already-sorted data that our textbook version plows through blindly), and it avoids allocating on every merge. None of that changes the O(n log n) — both lines have the same shape — which is the reassuring result. You built the algorithm the library is built on; the library just runs it faster. And you got stability for free, the same property sorted guarantees, from the single decision to take the left element on ties.

Where you'll actually meet it

Merge sort is the sort behind stable sorting everywhere. Python's sorted and list.sort, Java's object sort, and Rust's stable sort are all Timsort or close relatives — merge sorts tuned for real data. Its sequential-access nature makes it the algorithm for external sorting: databases and big-data systems sort terabytes by merging sorted chunks streamed from disk, exactly von Neumann's idea at scale. It's the natural sort for linked lists, which quicksort can't touch efficiently. And the merge operation itself, independent of the sort, is a workhorse — merging sorted streams underlies log-structured databases, version-control diffs, and the merge step of external joins.

Takeaways

Merge sort splits the array in half, recursively sorts each half, and merges the two sorted runs — $O(n \log n)$ in every case because the split is data-independent, and stable because ties break left. The cost is $O(n)$ extra memory for the merge. Its guarantee (no bad case) and its stability make it the sort of choice when you can't predict the input or need to preserve order, and its sequential access makes it the sort for data bigger than memory.

The next chapter is its great rival, quicksort — also O(n log n) on average, also divide-and-conquer, but in-place and usually faster in practice, at the price of an O(n²) worst case merge sort doesn't have. Comparing the two is the clearest lesson in the book on how the same asymptotic class can hide very different real-world trade-offs.