Natural run — where it appears
Named by 2 essays across one field — 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.
Named alongside it
The objects these essays reach for when they reach for this one.
Library sortTimsortAdaptive sortComparison countComplexity classCutoffInsertion cutoffIntrosortInversionsJavaMerge policyminrun