Why does Timsort merge runs eagerly under stack invariants instead of merging them all at the end?

## The design question Run detection produces a sequence of ordered runs. Something has to decide **when** and **in what order** to merge them. Two extremes bracket the design space. Merge every new run into the accumulated result immediately, and you get a linear chain: run 2 merged into run 1, run 3 into that, and so on. Each merge touches the whole accumulated prefix, so with `r` runs the total cost is O(r * n) — quadratic when runs are many. Defer everything and merge at the end, and you must hold all `r` runs, which is up to `n/min_run` stack entries, and you still have to decide an order. Nothing prevents a bad order. Timsort takes a middle path: push runs onto a stack and, after each push, merge just enough to restore size invariants over the top few entries. ## The invariants With the three topmost run lengths named `Z`, `Y`, `X` from deepest to shallowest, the rules are: - `Z > Y + X` - `Y > X` After pushing a run, a collapse loop checks these and merges until they hold. When `Z <= Y + X` is the violation, it merges `X` with whichever neighbour is smaller (`Z` with `Y`, or `Y` with `X`) so the result stays balanced; when only `Y <= X` is violated, it merges `Y` with `X`. ``` // stack of run lengths; X = top, Y = second, Z = third while stackSize > 1 if stackSize > 2 and Z <= Y + X if Z < X merge(Z, Y) else merge(Y, X) else if Y <= X merge(Y, X) else break ``` ## What the invariants buy **A logarithmically bounded stack.** `Z > Y + X` forces lengths going down the stack to grow at least as fast as the Fibonacci sequence, so the depth for an input of size `n` is O(log n) with a small constant — a few dozen entries even for enormous arrays. That lets an implementation preallocate a fixed-size stack instead of growing one dynamically, which is a real engineering win in a hot library routine. **Balanced merges.** Merging runs of comparable size is what keeps merge sort's total work at O(n log n). Every merge of a small run into a very large one pays a full sweep of the large run for a handful of newly placed elements. The invariants make that shape impossible: nothing tiny sits on top of something enormous for long. **Bounded memory and better locality.** Merging as you go means the temporary buffer only ever has to hold the smaller of two adjacent runs, and the data being merged was touched recently. **Stability.** Only adjacent runs are merged, ever. This is not an optimisation, it is the stability guarantee: if runs A, B, C sit in input order and you merged A with C, an element of A equal to one in B would end up positioned relative to B by accident of the merge order, and the input order among equals would be lost. Adjacency is what makes the merge's tie rule — take from the earlier run first — sufficient to preserve order globally. ## The correctness story The collapse rule above is the version that shipped for years and is the one most references describe. In 2015 a formal-methods team attempting a machine-checked proof of the algorithm found that checking only the top three entries does **not** guarantee the invariant holds all the way down the stack. Crafted inputs can leave a deeper violation unrepaired, letting run lengths grow more slowly than the analysis assumed, so the stack can exceed the preallocated bound and overflow. The consequence is worth stating precisely, because candidates guess wrong here: the output does not come back mis-sorted and equal elements do not get reordered. The failure is an out-of-bounds access on the preallocated run stack. Two fixes exist and both are in the wild — check one more entry in the collapse loop so the invariant genuinely holds, or simply enlarge the preallocated stack so overflow is unreachable. Java and Python implementations both carried the flaw and responded differently, one enlarging the stack, the other later replacing the merge-ordering policy outright with a newer near-optimal scheme. The reason to know this story is not trivia. It is a concrete demonstration that a widely deployed library routine, reviewed for a decade, carried a reachable bound violation that only a proof attempt exposed — and that the fix was a change to a five-line invariant check, not a redesign. ## What to say when asked State the two invariants, explain both payoffs (bounded stack, balanced merges), give adjacency as the stability requirement, and close with the honest note that the original rule was proved insufficient and the failure mode was stack overflow rather than incorrect output.