Merge sort

Merge sort is usually introduced by splitting an array in half, then in half again, until every piece is one element long, then merging back up. That version is correct, easy to reason about, and not what your language actually runs. The gap between the two is worth understanding, because it is all about an assumption the textbook makes and real data does not honour.

The merge is the whole algorithm#

Take two sequences that are each already sorted. Look at the first element of each, take whichever comes first, and repeat. Every step consumes exactly one element and never looks backwards, so combining two sorted stretches costs one pass over both of them. Nothing about that step is clever, and that is the point — it is so cheap that the whole design becomes a question of how to get sorted stretches to feed it.

The textbook answer is to keep splitting until the pieces are trivially sorted by virtue of holding one element each. It works, and it treats a sorted input exactly the same as a shuffled one, doing the full ceremony of splitting and merging either way. That is a strange thing to do given how much real-world data arrives partly ordered — appended logs, records read out of an index, a list re-sorted on a second key after being sorted on a first.

Real data is not random#

CPython 3.14’s implementation notes describe discovering non-decreasing or non-increasing runs. This avoids needlessly breaking existing order into singleton runs. For the ordinary buffered textbook algorithm, each merge level touches O(n) elements and there are O(log n) levels: O(n log n) time, O(n) buffer space, and O(log n) recursive stack space.

Reversing a descending run takes linear work in its length; it is not free. Equal keys require care: CPython 3.14 first reverses equal-key subruns, then reverses the whole descending run, restoring the original order within ties. Older descriptions used strictly decreasing runs to avoid this issue. Adaptive sorting can reduce comparisons on already ordered data; it does not eliminate the work of inspecting the input.

Two further adaptations follow from taking real data seriously. Very short runs are extended to a computed minimum length so the merges stay balanced, with that minimum chosen from a small range to make the number of runs land on or just under a power of two. And when one run keeps winning the comparison, the merge switches to galloping — searching ahead exponentially rather than one element at a time, on the reasoning that clustering reveals itself by how often the winner comes from the same run. Both are the same instinct as a sort that adapts to what it finds rather than trusting its own average case.

What stability actually promises#

A stable sort keeps elements that compare equal in the order they arrived. That sounds like a technicality until you sort on two keys in succession: sort by name, then by department, and a stable sort leaves each department’s people still in name order. An unstable one silently scrambles the first sort, and the result looks close enough to correct to survive review.

In a forward merge, take the earlier run first when the two front keys compare equal. With stable input runs, that preserves original tie order. The straightforward implementation pays for an output buffer so it can merge in one pass without overwriting unread elements. More elaborate in-place algorithms exist; the buffer is a property of this implementation, not a theorem that merging must allocate O(n) extra memory.

Change the merge tie rule

Earlier run: [1-A, 2-B]. Later run: [1-C, 3-D]. Letters record original identity; compare only the numbers. Will equal records keep their order?

When the front keys tieTake earlier run firstTake later run first

Earlier-first merge: 1-A → 1-C → 2-B → 3-D. Equal key 1 preserves A before C.

Consume next recordReset merge

Enable JavaScript to change the trace. The initial worked result above remains readable.

Two already sorted adjacent runs, fixed numeric comparator. This models only merging and stability, not a complete library sort or an in-place merge.

The contrast is visible in selection sort: its usual minimum-swap implementation uses constant extra space and few writes, but one swap can reverse two equal records.

The ordering constraint also shapes the merge itself. CPython’s notes explain that with three consecutive runs in hand it dare not merge the first with the third, because elements would end up out of order relative to the run between them — so merging always takes two consecutive runs. Stability is not a property bolted on at the end. It is a restriction on which merges the algorithm is permitted to perform, and the same care about where equal elements sit shows up wherever ordering and equality are allowed to disagree.

Questions people also ask

4 QUESTIONS

▸ Is the sort in my standard library a merge sort?

Often a descendant of one rather than the textbook version. CPython's sort is documented in its own listsort.txt as a merge sort adapted to find ordering that already exists in the data, and Java uses a comparable approach for objects. The merging step is the same; what changed is that the runs are discovered rather than manufactured by splitting down to single elements.

▸ What is a run?

An ordered stretch of input. CPython 3.14 recognizes non-decreasing and non-increasing runs. To reverse a descending run stably, it first reverses equal-key subruns so the full reversal restores their original order.

▸ Why is merge sort stable when quicksort is not?

A merge preserves ties by taking the earlier run first. Common in-place quicksort partition schemes can move equal records past each other, but stable quicksort variants exist. Stability is an algorithm and implementation contract, not an impossibility attached to the name quicksort.

▸ Why does merge sort need extra memory when quicksort does not?

The straightforward array merge uses a separate output buffer. In-place merging algorithms exist, with more complicated movement and bookkeeping; this page teaches the buffered version. Quicksort also normally uses stack space, even when its partition step is in place.