minrun — where it appears
Named by 3 essays across 2 fields — each of them below, with the objects they name alongside it.
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.
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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
TimsortAdaptive sortComparison countCounterexampleCutoffDepth limitFormal verificationGallopingGuaranteeInsertion cutoffIntrosortInversions