Ranking — where it appears
Named by 10 essays across 6 fields — each of them below, with the objects they name alongside it.
Counting instead of timing
A stopwatch measures the laptop it runs on. A counter measures the algorithm. Every number on this site comes from an array that increments a tally each time it is read, written, compared or swapped — which makes the counts exact, reproducible to the last digit, and identical on every machine that has ever built this page.
The count is not the time
An operation count is exact, machine-independent, and not a running time. The gap between them is mostly memory, and it is large enough to reorder the rankings. This site carries a second count — modelled cache misses from the same runs — and asserts that the two disagree, because if they agreed the second one would carry no information.
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.
How close anything gets to the floor
The interesting question about a sorting algorithm is not its complexity class but its distance from the bound nothing can cross. Merge sort comes within 2.2% of the information-theoretic floor. Heapsort uses 96% more than it needs to. Selection sort uses nineteen times. Those three numbers say more than the classification does.
The constant the notation drops
Six algorithms on this site are Θ(n log n) and their comparison counts differ by a factor of two. The class is what they have in common; the constant is what distinguishes them. It is measurable to three digits, it is the number that actually decides between them, and it is precisely the number the classification is designed to discard.
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.
The frontier between time and space
The question of which sorting algorithm to use has an honest answer, and it is a shape rather than a name. Comparisons on one axis, peak auxiliary space on the other, and five of the ten algorithms here are on the Pareto frontier while five are dominated — beaten on both counts at once, so that no weighting of the two costs makes them the right choice. Heapsort is one of the five that lose.
The count somebody chose
Six quantities can now be measured for every sort. Ranking the ten algorithms by each of them and comparing the orders, comparisons and peak space disagree about 91% of all pairs, and memory traffic and modelled misses disagree about 7%. There is no ranking of sorting algorithms; there are six, and choosing between them is a statement about the data rather than about the algorithms.
Where insertion sort actually wins
Every production sorting routine falls back to insertion sort on small subarrays, and the usual explanation is that below some threshold it does fewer comparisons. Measured, it does not — not at sixteen elements, not at eight, not at four. The crossover is real and it is entirely in memory traffic, which is a distinction the usual telling loses.
The exchange rate nobody wrote down
Three earlier essays have said in passing that the ranking would change if the elements were large records. None of them computed it. Computed, selection sort goes from second-worst of seven at four bytes a record to best of seven at five hundred and twelve — and the crossover against each rival is a division that takes one line.
Named alongside it
The objects these essays reach for when they reach for this one.
Comparison countQuicksortCacheCost modelCutoffPivotSwapsTrade offDistributionBenchmarkingComplexity classConstant factor