Timsort — where it appears
Named by 9 essays across 4 fields — each of them below, with the objects they name alongside it.
The sort the library ships
Every sorting algorithm measured on this site so far has one thing in common — none of them is what runs when a program calls sort. Python, Java, Rust and Android run Timsort; C++ runs introsort; Java's primitive sort is dual-pivot quicksort. Not one of the four was in this collection, and the reason it matters is that they are not algorithms in the sense the other essays use the word.
A run is a property of the input
A benchmark that says "nearly sorted" never says how nearly. It is a recipe with a seed, not a measurement, and an adaptive bound stated against it is a bound with an undefined second parameter. Counting the natural runs turns the shape of an input into a number — and then Timsort's bound becomes something that can be fitted rather than quoted.
When galloping pays
Timsort's merge does not always take elements one at a time. When one run has won seven times in a row it switches to searching for how many to take at once, and switches back when that stops paying. The mode saves 22,104 comparisons on nearly sorted input, 33,270 on input with few distinct values, and costs exactly six on random input — which is the whole design in three numbers.
The branch the machine guesses
Insertion sort does 176 times as many comparisons as Timsort at n = 8,192 and mispredicts a sixth as many branches. Merge sort's inner test is a coin flip and misses 51.5% of the time; selection sort's misses 0.6%. A processor does not wait to learn the answer to a comparison — it guesses, and throws away the work when it guessed wrong — and this is the fifth quantity this site counts.
The threshold somebody chose
A minrun of 32. An insertion cutoff of 16. A gallop threshold of 7. A depth limit of twice the logarithm. Four numbers, in four real source files, none of which appears in any complexity analysis — and each of which decides more about what these algorithms do than the analysis does. Swept, they turn out not to be optima, and finding out what they are instead is the point.
A search with no branch to miss
A binary search does about log₂ n comparisons and every one of them is a coin flip, so it mispredicts once per level. Writing it so the comparison feeds an index instead of a jump costs two thousand extra comparisons over two thousand searches and takes the mispredictions from 17,993 to 2,001 — flat in n, at every size. Under the counters this site had a phase ago, that is a strictly worse algorithm.
Two pivots and what they cost
Java changed its primitive sort in 2011 on the strength of an analysis showing dual-pivot quicksort does fewer comparisons than the classical one. It does. It also does nearly twice the swaps, and the analysis that decided the matter counted neither — it counted a weighted combination that had to be chosen before any conclusion could be drawn.
The invariant that was wrong for seven years
Timsort's merge policy is supposed to keep its run stack shallow, and the rule that enforces it inspects the top three entries. In 2015 a group of formal-methods researchers proved that the rule does not imply what it was believed to imply. Thirty-three elements are enough to break it, the array still comes out perfectly sorted, and the defect is in a structure that nothing about the output can show.
The count that came from somewhere else
Every count in these essays is described as exact, reproducible, and identical on every machine. Two of them are not. A spanning-tree measurement quotes 42,385 comparisons spent in a sort, and that sort is the language's own — whose comparison count is specified nowhere, varies by a factor of thirteen across input kinds, and comes within one per cent of the information floor on random input.
Named alongside it
The objects these essays reach for when they reach for this one.
Comparison countIntrosortAdaptive sortCutoffJavaMerge policyminrunMispredictionPivotQuicksortBinary searchBranchless