Merge sort
Merging two sorted runs is trivial and is the whole algorithm. What separates the textbook version from the one in your standard library is where the runs come from — real data arrives with ordered stretches already in it, and a good implementation looks for them first.
Think of merging two already-alphabetised piles of paper. You only ever compare the top sheet of each and take the earlier one, so a thousand sheets take a thousand glances. The clever part is noticing which stretches of the pile were in order before you started.
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’s sort is documented in a file that ships with the source, listsort.txt, and it starts from the observation the textbook skips: the input probably contains ordered stretches already, so find them instead of manufacturing them. It calls such a stretch a run, defined as either ascending, meaning non-decreasing, or descending, meaning strictly decreasing — and notes a run is always at least two long unless you begin at the last element.
Two details in that definition are load-bearing. A descending run is turned into an ascending one by reversing it in place, which is free; and the asymmetry — non-decreasing for one, strictly decreasing for the other — exists so that a stretch containing equal neighbours is never reversed, because reversing it would swap two equal elements and break the stability guarantee below. The payoff is stated in the same file: on partially ordered input the algorithm needs less than lg(N!) comparisons and as few as N-1, which is the best any comparison sort can do on data already in order.
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.
Merging gives stability almost for free, because the tie has an obvious rule — when the fronts of two runs compare equal, take from the earlier run. What it costs is somewhere to put the output, since two sorted stretches cannot be merged in place without giving up the single linear pass. That is the real trade against an in-place sort, and it is why the same standard library will often use one algorithm for objects, where stability is expected, and another for primitives, where there is no way to tell two equal values apart.
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.
IF YOU REMEMBER ONE THING
Merging sorted runs is the easy part. Every difference between the algorithm you were taught and the one you actually call is about where the runs come from — and the good implementations assume your data already contains some.
Questions people also ask
4 QUESTIONSIs 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?
A stretch of the input that is already in order. CPython's notes define one as either ascending, meaning non-decreasing, or descending, meaning strictly decreasing, and observe that a run is always at least two long unless you start at the last element. Descending runs are handled by reversing them in place, which is why the strictness matters — reversing a stretch with equal neighbours would disturb their order.
Why is merge sort stable when quicksort is not?
Because merging can break ties by rule and partitioning cannot. When the front elements of two runs compare equal, the merge takes the one from the earlier run, so equal elements keep their original order. Quicksort's partition swaps elements past each other with no regard for where they started, which is why libraries that guarantee stability build it on a merge.
Why does merge sort need extra memory when quicksort does not?
Because the merge writes its output somewhere other than where it reads. Two sorted stretches cannot be combined in place without either moving a great deal of data or giving up the linear-time merge that makes the algorithm worth using. Real implementations reduce the extra space rather than eliminate it, and accept the cost in exchange for a predictable worst case.