Stability — where it appears
Named by 5 essays across 2 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.
One run, four counts, four answers
The question “how many operations” has no answer until the operation is named. Selection sort makes more comparisons than any other algorithm here and fewer writes than almost all of them; bubble sort matches its comparisons and does 124 times the swapping. The ranking depends entirely on which count is chosen, and the choice needs justifying.
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 order equal keys keep
Four of the eight sorts here leave every pair of equal keys in the order it arrived in and four move between 1,209 and 2,403 pairs, and none of the four counts every plate here reports can tell them apart. Decorating each record with its arrival position makes any of them stable, for four thousand words and between 0.05 and 1.64 times its comparisons — a charge of 64% on Shellsort and a saving of 95% on quicksort, because the ties stability has to break are the ties a two-way partition chokes on.
The sort that makes none of them
Every count on this collection is a count of comparisons, swaps, reads or writes, and radix sort makes zero of the first. On 65,536 keys it moves five times less data than merge sort, misses the cache three times more, and sits 954,037 comparisons under the floor no comparison sort can go beneath — which is not an achievement, because the floor was never a statement about it.
Named alongside it
The objects these essays reach for when they reach for this one.
Comparison countQuicksortCacheCounting conventionCutoffIntrosortMeasurement designMerge policyPartitionPivotRankingSpace time trade