Ranking — where it appears
Named by 13 essays across 7 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. A second count is kept alongside it — modelled cache misses from the same runs — and the two are required to disagree, because if they agreed the second one would carry no information.
The sort the library ships
Every sorting algorithm measured in these essays 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.
The commonest word at the distance
A spelling checker that lists every nearest word counts a correction whenever the intended word is somewhere in the list, and on a short query that list averages three or four words. Offering only the commonest of them was predicted to keep nine in ten of the list's corrections on short words when misspellings follow use, and far fewer when they are drawn evenly from the word list. It keeps 77% on words of three or four letters, and on the even stream it keeps 48% — less than a choice that ignores the counts. Across all lengths the two streams look the same, which is how the difference stays hidden.
A list as long as the doubt
A spelling checker that offers one word is right 64% of the time on short misspellings, and one that offers three is right 80% of the time. Between them sits the obvious design: one word when the commonest nearest word's count dominates the next, more when the counts are close. The counts do know when the commonest word is right, from 36% of the time at a ratio under two to 91% over a hundred. Yet a list sized by that ratio beats a blind mix of one word and three by at most two and a half points, a plain list of two does as well, and on misspellings drawn evenly from the word list the ratio is worse than not reading it.
A second word judged by its own share
A spelling checker that offered its commonest nearest word alone when that word's count was many times the next, and two or three words otherwise, beat a coin's mix of one-word and three-word lists by at most two and a half points, and a plain list of two did better. The ratio measures how dominant the first word is, not how likely the second is. Judged instead by its own share of everything within two edits of the misspelling, the second word is shown only when that share is at least 0.15: on short words drawn by use the checker then sits 4.5 points over the coin's line at 1.32 words a query, nearly twice the ratio's lift and above the list of two, and the weight given a two-edit word moves the result by a tenth of a point. A second word with a share under 0.01 is never the source. On misspellings drawn evenly the share is no guide at all, and the list of two wins.
Named alongside it
The objects these essays reach for when they reach for this one.
Comparison countQuicksortCacheCost modelCutoffMeasured countPivotSwapsTrade offCorpusDistributionEdit distance