Merge Sort: Why Stability Survives the Merge and What the Buffer Costs

Merge sort’s structure is two recursions and a merge, and the merge is where every interesting property is decided. The comparison count is fixed near the information-theoretic floor, stability either holds or fails depending on one branch condition, and the extra array is not an implementation detail but a requirement of the straightforward formulation. Each of these follows from the merge loop rather than from the recursion.

The merge invariant

The merge takes two sorted runs and produces one sorted run. It maintains an index into each input, always emitting the smaller of the two front elements. The correctness argument is an exchange argument: the emitted element is the minimum of all remaining elements, because each run is sorted, so each run’s front element is its own minimum. The output is therefore sorted.

The comparison count for merging runs of length $m$ and $n$ is between $\min(m,n)$ and $m+n-1$. The lower end happens when one run’s elements are all smaller than the other’s, so the merge exhausts one side and copies the rest without comparing. The upper end happens when the runs interleave, so all but one element requires a comparison. Summing across a balanced recursion tree gives a total between $\tfrac{1}{2} n \log_2 n$ and $n \lceil \log_2 n \rceil - n + 1$; the only inputs that reach the lower end are those already in sorted or reverse-sorted blocks matching the split boundaries, because that is what it takes for one side to win every comparison at every merge.

One condition decides stability

Stability means equal keys keep their input order. In the merge, stability is a property of the tie rule:

/* merge a[lo..mid) and a[mid..hi) into tmp, then copy back */
size_t i = lo, j = mid, k = lo;
while (i < mid && j < hi) {
    if (a[i] <= a[j]) tmp[k++] = a[i++];
    else              tmp[k++] = a[j++];
}
while (i < mid) tmp[k++] = a[i++];
while (j < hi)  tmp[k++] = a[j++];

With <=, when the fronts are equal the left run’s element is emitted first. Every element of the left run originated at a lower index than every element of the right run at the level where they were split, and that is exactly the input order. With < instead, the right run’s element is emitted first on a tie, and equal keys come out reversed relative to input: the sort becomes unstable.

The recursion preserves this at every level. Each merge of two runs preserves the relative order of equal keys within and across those runs, so by induction the final output preserves the input order of all equal keys. This is why merge sort is the stable sort of choice when the comparator is a single key and the record has other fields whose order must survive, and why the same tie rule appears verbatim in Timsort’s merge.

The buffer, and the three ways to avoid allocating it

The straightforward merge needs a destination buffer of the same size as the merged output, because writing in place would overwrite elements not yet read. That is $\Theta(n)$ extra space, and it is allocation that matters as much as capacity: a fresh malloc per merge level would be $n \log n$ bytes allocated over the run.

The three standard remedies differ in what they trade.

Allocate once. Allocate a single buffer of size $n$ at the top and pass it down. Space stays $\Theta(n)$, but allocation count drops to one. The recursion depth is $\Theta(\log n)$ frames, so stack usage is logarithmic.

Merge into the buffer and swap. Instead of copying the merged output back into the input array, alternate the roles of the two arrays at each level. The cost is that the caller cannot know which array holds the result without tracking the parity of the recursion depth, so the top-level call must either copy once at the end or return a pointer to the result. This removes the copy-back pass but not the buffer.

Merge in place. In-place merging exists and costs more comparisons and moves. The simplest correct version rotates one element at a time, which is quadratic. Better versions use binary search to find where a block of the left run belongs in the right run, then rotate the block into place, keeping the merge at $O(n \log n)$ moves per merge with $O(1)$ extra space. A bottom-up merge then performs $O(n \log^2 n)$ moves in total, and the constant is worse than the buffered version by a wide margin. Practical implementations use the buffer; in-place merging is for the case where memory is genuinely unavailable.

A middle option used by some libraries is to allocate a buffer of bounded size, merge in blocks, and fall back to rotation for the remainder. That caps memory at a constant while keeping the common case fast, at the cost of a more complicated merge.

Natural runs make the algorithm adaptive

Textbook merge sort starts from runs of length 1. Real data is rarely random, and the recursion can start from whatever ascending runs already exist. Scan the input, record the boundaries of maximal non-decreasing runs, and merge adjacent runs until one remains.

Cost is then $O(n \log r)$ comparisons where $r$ is the number of initial runs, not $n$. Fully sorted input has $r = 1$ and costs one linear scan; reverse-sorted input has $r = n$ unless descending runs are detected and reversed, which costs one pass and reduces $r$ to 1. Timsort does exactly this, plus two refinements: it extends short runs to a minimum length using insertion sort, and it merges runs according to a stack invariant that keeps run lengths roughly balanced.

The invariant matters because an unbalanced merge schedule can be quadratic. Merging a short run into a much longer one repeatedly copies the long run, so a sequence of small runs adjacent to one large run can cost $O(n^2)$ moves even though every individual merge is linear. Timsort keeps a stack of runs and merges the top entries whenever their lengths violate a size-ordering invariant, chosen so that lengths along the stack grow at least geometrically. That bounds the stack depth logarithmically and bounds total merge work at $O(n \log n)$, which is a property a merge schedule has to earn rather than assume.

Galloping and the cost of lopsided merges

When one run is much longer than the other and their elements do not interleave, a plain merge still compares at every step of the long run. Galloping replaces the linear advance with an exponential search: probe ahead in the long run at offsets 1, 2, 4, 8, and so on until an element larger than the short run’s front is found, then binary search in that interval. A block that would have cost $k$ comparisons costs $O(\log k)$, and the block is then moved wholesale.

The condition for using it matters as much as the technique. Galloping only pays when a long stretch of one run wins consecutive comparisons; applied to interleaved runs it costs more than the linear scan. Implementations trigger it only after a threshold number of consecutive wins from the same side.

What merge sort does not do well

The buffer traffic is the practical cost. Every level reads and writes $n$ elements, so total memory traffic is $\Theta(n \log n)$ element transfers, and for inputs larger than cache the sort is bound by memory bandwidth rather than comparison count. Quicksort, which partitions in place with sequential scans, moves less data per level and usually wins on large arrays despite more comparisons. That trade is the subject of quicksort partition schemes.

Merge sort’s other weakness is that it cannot exploit a good pivot choice the way quicksort can, and it has no natural way to bound worst-case stack depth beyond the recursion’s logarithmic depth. Both are acceptable, and the predictability is the reason it is the sort used for data larger than memory, where sequential access and mergeable sorted runs are the only things that matter.