The sort the library ships

Forty-six essays into this collection there are ten sorting algorithms in lib/algorithms.js, each measured across three orders of magnitude, each with its declared complexity class fitted and granted or refused. Insertion sort, selection sort, bubble sort, merge sort, heapsort, three quicksorts, Shellsort, and a merge sort with a cutoff.

Not one of them is what runs when a program sorts something.

Python’s sorted and list.sort run Timsort. Java’s Collections.sort runs Timsort. Rust’s slice::sort runs Timsort. Every Android phone runs Timsort, because Android’s runtime inherited Java’s. C++'s std::sort runs introsort, and increasingly pdqsort. Java’s Arrays.sort on primitives runs dual-pivot quicksort. Between them these four account for a very large fraction of all the sorting that has ever been done, and this site has had nothing to say about any of them.

That gap is easy to describe as a coverage problem and it is not one. Adding four more rows to the growth curves would be coverage. The difficulty is that these four are not the same kind of object as the ten, and the difference is what this whole field is about.

A procedure has a complexity; a policy has thresholds #

Merge sort is a procedure. Given an array it does one thing, always, in one order, and its cost is a function of the array’s length and nothing else. That is why the audit above works: there is a single number to measure and a single curve to fit, and the fit either holds or it does not.

Timsort is not like that. Timsort is a set of decisions:

• Find the natural runs. Scan forward while the elements ascend; if they descend instead, scan while they descend and then reverse the stretch in place. This is a decision about the input, taken before any sorting happens.
• Extend short runs. If a run is shorter than minrun, take the next few elements and binary-insert them into it. minrun is a number between 32 and 64, computed from the array’s length by a rule that fits in five lines.
• Push it on a stack, then merge according to a policy. The stack of pending runs is not merged in arrival order and it is not merged only at the end. After every push, a rule decides which adjacent pair to merge now.
• Merge, and switch modes if one side keeps winning. The merge takes elements one at a time until one run has won MIN_GALLOP times in a row, then switches to searching for how many to take at once, and switches back when that stops paying. MIN_GALLOP is 7, and it moves during the run.

Every one of those four carries a constant, and none of the constants appears in any complexity analysis of Timsort. The bound is $O(n \log n)$ with or without them. The behaviour is not.

The five input kinds along the left of that figure have been the site’s vocabulary since the first essay. What the run map shows is that they are five points in a space, and that Timsort’s cost is a function of where an input sits in that space rather than of which name it was given. That is the subject of a run is a property of the input, and it is the first thing the practice field makes measurable.

What the run detection is worth, in one number #

The clearest measurement in this essay needs no explanation at all.

Sort an already-sorted array of 8,192 elements. Merge sort takes 53,248 comparisons. Timsort takes 8,191.

Sort a reversed array of 8,192 elements. Merge sort takes 53,248 comparisons — the same, because it does the same work on every input. Timsort takes 8,191 again.

Both of those are exactly $n - 1$, which is the smallest number of comparisons that can establish that an array is in order. Timsort spends the minimum possible and stops, because the run scan finds one run, there is nothing to merge, and it is done. The reversed case costs the same because a descending run is not a worst case for Timsort: it is detected as a run and reversed in place, which costs swaps and no comparisons at all.

That second point is worth dwelling on, because it is a design decision that could easily have gone the other way, and the reason it went this way is stability. Timsort’s ascending test is non-strict — it extends a run while a[i] >= a[i-1] — and its descending test is strict, a[i] < a[i-1]. If the descending test were non-strict it would sweep up runs containing equal elements, and reversing such a run would exchange the order of equal elements, and Timsort would not be a stable sort. The asymmetry between two comparison operators, one line apart, is the whole of Timsort’s stability guarantee on descending input.

Adaptivity is not free, and the price is visible #

It would be easy to read the previous section as Timsort dominating merge sort, and the measurement does not say that.

On random input at n = 8,192, Timsort takes 95,772 comparisons and merge sort takes 96,140. That is a difference of 0.4%, which is to say: on the input that no run detection can help with, all the machinery above buys essentially nothing. Timsort is a merge sort, its merges are merge sort’s merges, and when there is no structure to find, finding none costs about what it saves.

The right way to read that is not disappointment. It is the shape of every adaptive algorithm: pay a small fixed cost to look, in exchange for a large saving when there is something to see. The scan for runs costs $n - 1$ comparisons on every input, always, and that is 8,191 of Timsort’s 95,772 on random input — 8.6% — recovered because the runs it does find, short as they are, do not have to be re-established by the merges.

The cases where the machinery earns its cost are the ones a real program actually sorts. Data that arrives sorted, data that arrives in a few sorted batches, data that was sorted by a different key last time. Nearly sorted input at n = 8,192 costs Timsort 33,449 comparisons and merge sort 53,790 — a saving of 38%, on an input that is not contrived and not rare.

The audit had to change its range, and the reason is the field’s #

The hero figure at the top of this essay is fitted from n = 256 to n = 16,384. Every other audit on this site starts at 32. That is not a stylistic difference and it is worth explaining, because working out why took a wrong answer first.

Fitted from n = 64, pattern-defeating quicksort’s comparison count on reversed input gives a spread of 2.19 against the site’s tolerance of 1.6, and the class $n \log n$ is refused. Fitted from n = 256 the same algorithm on the same input gives 1.11 and the class is granted. Nothing changed but the two smallest sizes.

The site has met this shape before. The cliff where the data stops fitting is about a fit that changes its answer when the range is extended, and the honest conclusion there was that a measured class is a claim about a stated range. But this is a different cause, and a more interesting one.

At n = 64, pdqsort’s insertion cutoff is 16 and its ninther pivot selection does not engage below 128. A run at that size is one partition and then insertion sort. What the fit measures at n = 64 is the cutoff, not the algorithm — and the cutoff is insertion sort, whose class is not $n \log n$ at all.

Every one of these four has that property. Introsort stops at 16 elements. Dual-pivot quicksort stops at 17. Timsort’s minrun means it never merges anything shorter than 32, so an array of 32 elements is sorted entirely by binary insertion and Timsort’s merge machinery never runs at all.

So the statement “Timsort is $O(n \log n)$” is a statement about what Timsort does above its own thresholds, and the thresholds are hundreds of elements wide. That sentence was never needed for the ten textbook sorts, because none of them has a threshold. It is needed for all four of these, and it is the first sign that the object being analysed has changed shape.

The range is stated in LIBRARY_RANGE, it is printed on every figure that uses it, and the gate fits against it. A claim measured over a range that includes the algorithm’s own special cases is a claim about the special cases.

Four algorithms, four different answers #

The other three library sorts are not merge sorts and they answer the same problem differently.

On comparisons alone Timsort wins on random input, and that ranking survives exactly as far as the next counter.

Timsort’s peak auxiliary space at n = 8,192 is 4,097 slots. Introsort’s is 28. That is not a small difference and it is not a technicality: it is the difference between an algorithm that can sort an array occupying most of available memory and one that cannot. It is also exactly why C++ has both std::sort and std::stable_sort, and why std::stable_sort is documented to fall back to a slower algorithm when it cannot get its buffer.

So there is no ordering of these four. Which is best depends on which counter, and the counters disagree — which is the site’s oldest theme, arriving in a field where the disagreement is not an observation about algorithms but the actual reason four different ones exist in four different standard libraries.

That last point is worth making concretely, because the four choices are not arbitrary and each of them is a constraint written down somewhere.

Java has two sorts because its language specification requires one of them to be stable. Collections.sort, which sorts objects, must not reorder elements that compare equal, because an object’s identity is not its sort key and a program sorting by surname after sorting by first name is relying on it. Arrays.sort on int[] has no such obligation — two equal ints are indistinguishable, so stability is not observable — and so it is free to use dual-pivot quicksort and to keep the memory. One language, one library, two algorithms, and the reason is a property no counter on this site measures.

C++ has two sorts because it will not hide an allocation. std::sort promises $O(n \log n)$ and no allocation; std::stable_sort promises stability and is allowed a buffer, and is documented to degrade to $O(n \log^2 n)$ if it cannot get one. Introsort is the answer to the first promise: it is quicksort, which allocates nothing, with a fallback that turns the quadratic case into a guarantee.

Rust has two sorts because it made the same split and named it differently — sort is Timsort-derived and allocates, sort_unstable is pdqsort and does not.

Three libraries, the same fork in the road, three different pairs of answers. None of the six is better than the others and each of them is a different reading of what a caller is entitled to assume.

What the apparatus costs, measured where it can do nothing #

The random-input row is usually read as a disappointment — all that machinery for a 0.4% difference — and it is better read as the strongest number in this essay, because it is a measurement of the overhead itself.

On random input there is nothing for the run scan to find, nothing for the merge policy to balance that a plain merge sort would not have balanced, and nothing for galloping to exploit. Whatever the four decisions cost, they are paid in full and repaid by nothing. So the difference between Timsort’s 95,772 comparisons and merge sort’s 96,140 is an upper bound on the price of the entire adaptive apparatus, in this column, on any input — and the difference is 0.4% in Timsort’s favour.

Set that beside the payoff. Nearly sorted input: 33,449 against 53,790, a saving of 38%. Sorted or reversed: 8,191 against 53,248, a saving of 85%.

A mechanism whose worst case is a 0.4% saving and whose ordinary case is a 38% one is not a trade at all. That is the answer to the question a reader is entitled to ask about all four decisions above — whether looking for structure is worth the looking — and the answer is that the looking has no measurable cost in comparisons even when it finds nothing.

Which is a stronger claim than the arithmetic first suggests, because the scan alone is $n - 1$ comparisons — 8,191 of the 95,772, or 8.6% of the total. That 8.6% is spent on every input, and on random input it still comes out ahead of merge sort, so the runs it finds must be worth slightly more than they cost even when the mean run is 1.5 elements. The scan is not overhead recovered by adaptivity; it is work the merges would otherwise have done.

The caution is the one this essay makes two sections later and it applies to this section hardest. The apparatus is free in comparisons and is not free. Timsort’s peak auxiliary space at $n = 8{,}192$ is 4,097 slots against introsort’s 28 — a factor of 146 — and that is where the merge structure is actually paid for. A reader who took “0.4% overhead” from the column above and concluded that the machinery is close to costless would be making precisely the single-counter mistake one run, two counts is about, on the site’s own flagship example.

So the honest summary is two sentences rather than one. The run detection, the minrun extension, the merge policy and the galloping check together cost nothing measurable in comparisons and buy between 38% and 85% on structured input. What they cost is a buffer, and the buffer is why three standard libraries ship a second sort beside this one.

A run is a property of the input is where the 38% becomes a curve rather than a point, and where the structure that produces it stops being an adjective.

The scoreboard on three more inputs #

Four algorithms and one input is a ranking of four algorithms on one input, which is the thing this field exists to stop anybody quoting.

The second input is not another ordering but another shape of data, and it is the one where the partitioning strategy rather than the run detection decides the ranking.

The stack nobody sees #

One more piece of Timsort deserves its own picture, because it is the piece that will turn out to matter most.

The runs are not merged as they are found. They go onto a stack, and after each push a policy decides whether to merge the top two, the pair below them, or nothing. The policy’s job is to keep the stack shallow and the merges balanced — merging a run of ten against a run of ten thousand wastes almost all of the work, and a policy that let the stack simply grow would end up doing exactly that at the end.

That structure is invisible in every way this site has previously been able to measure. The array comes out sorted whatever the policy does. The comparison count barely moves. The picture above is the only evidence that the policy ran at all.

Which is precisely why the policy that Python shipped, and that Java copied, was wrong for seven years and nobody noticed. The rule inspects the top three entries of the stack and it does not imply what it was believed to imply; there are run-length sequences that leave the stack in a state the invariant forbids, and Java’s stack-size table was too small for them. That is the invariant that was wrong for seven years, and the counterexample turns out to fit in thirty-three elements.

What this field is for #

The ten textbook sorts were the right thing to build a measurement instrument around, because each one does a single thing and the count of that thing is the whole story. They are also, all ten of them, museum pieces.

The four here are not, and measuring them turns out to need three things the site did not have:

• A number for the shape of the input, because Timsort’s bound is in the number of natural runs and “nearly sorted” is a recipe rather than a measurement. That is the next essay.
• A way to sweep a threshold, because the constants are not the notation’s leavings — they are choices, and the interesting question about a choice is what the alternatives cost. That is the threshold somebody chose.
• A counter for branch behaviour, because three of the techniques in these four algorithms do more work by every counter this site owns and exist anyway. That is the branch the machine guesses, and it is the fifth quantity this collection measures.

A last observation, and it is the one that made this field seem worth a phase rather than a paragraph. Every line above was measured by the same Counted array that measured bubble sort in the first essay. Nothing about the instrument changed. What changed is what was pointed at — and forty-six essays of careful measurement had been pointed away from the code that actually runs.