Comparison count — where it appears
Named by 56 essays across 9 fields — each of them below, with the objects they name alongside it.
A structure made of coin flips
Insert the same 512 keys into a skip list twice, once sorted and once shuffled, from the same seed, and the two structures are identical — the same 11 levels, the same height for every key, the same silhouette. Nothing about the data reached the layout. The 1,064 coin flips did all of 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 words "on average" are not a number
Quicksort is Θ(n log n) on average. Six hundred runs at n = 512 give a distribution with a mean of 4,945 comparisons, a median of 4,908, and a worst case 32% above the mean. The average is a summary of that picture, it is the least interesting thing in it, and it is almost always the only thing reported.
The cost is the number of subproblems
The edit-distance recurrence, written down literally, makes 29,737 calls on a six-letter word and a seven-letter word. Written down with a table beside it, it makes 56. Nothing about the arithmetic changed, and the class did.
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.
What O-notation does not say
Big-O is a statement about a limit. It does not say how fast, it does not say which is better, it does not say anything at all about any particular n, and it discards precisely the factor that usually decides the answer. Knowing exactly what it claims is the difference between using it and being misled by it.
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.
What randomising the pivot buys
Quicksort taking the first element as its pivot costs 130,816 comparisons on an already sorted array of 512 — 27 times its cost on random data, and exactly the quadratic behaviour the algorithm exists to avoid. Randomising the pivot costs 5,490 on the same input. Randomisation does not make the bad case impossible; it makes it unchoosable.
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.
Where an algorithm looks
Plotted as index against time, every array access an algorithm makes becomes a picture that no count contains. Merge sort's is a set of sweeps. Heapsort's is a spray. Quicksort's is a narrowing triangle. These shapes decide how fast the algorithms run and they are entirely absent from the analysis that says all three are Θ(n log n).
In place is a claim, and it is usually wrong about quicksort
Heapsort holds one slot at its peak. Quicksort holds twenty-two at n = 4,096 on random input and 4,097 on a sorted one. Merge sort holds 4,110. All three are described with the same two words, one of the three descriptions is false, and the false one is the algorithm the phrase is most often attached to.
The space the model does not see
A slot is not a byte, a frame is not a slot, sixteen thousand allocations are not one allocation of the same size, and none of these numbers includes the input. The space counters are the newest instrument here and the honest account of what they miss is longer than the account of what they measure — including one bound this phase set out to demonstrate and could not.
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.
Counting the coin flips
A skip list spends 2.03 random bits per key and a treap spends exactly 32. Reservoir sampling spends 1,356,399 bits on a stream of 65,536 and a better version spends 9,380. None of those numbers appears in any complexity class any of these structures is described by, and none of the site's other three counters can see them.
The branch the machine guesses
Insertion sort does 176 times as many comparisons as Timsort at n = 8,192 and mispredicts a sixth as many branches. Merge sort's inner test is a coin flip and misses 51.5% of the time; selection sort's misses 0.6%. A processor does not wait to learn the answer to a comparison — it guesses, and throws away the work when it guessed wrong — and this is the fifth quantity this site counts.
The floor when the values repeat
log₂(n!) counts orderings of distinguishable things. Two hundred and fifty-six values drawn from eight distinct ones have 1,684 bits of permutation entropy and 739 bits of distinguishability, so the real floor is less than half the one every table quotes — and merge sort, which sits exactly on the quoted floor, is 2.3 times above the one that applies.
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.
A guarantee that depends on an allocation
The C++ standard promises std::stable_sort N log₂ N comparisons if enough extra memory is available, and N (log₂ N)² otherwise. On 65,536 keys the library's own structure, denied its buffer entirely, makes 1,366,510 comparisons — a third more than with it, and twelve times under what the standard allows. What it spends instead is moves: 10.4 million against 1.2 million, 94% of them rotations. The standard bounds the count that barely changes and says nothing about the one that grows as n log² n.
Two searches, one comparison count
Three arrangements of the same binary search tree over the same million keys, walking the same path, making the same twenty comparisons. One costs 15 block transfers, one costs 13, and one costs 3. Nothing about the algorithm differs between them — only where the nodes were put — and no counter this site had before this phase could tell them apart.
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 count that came from somewhere else
Every count in these essays is described as exact, reproducible, and identical on every machine. Two of them are not. A spanning-tree measurement quotes 42,385 comparisons spent in a sort, and that sort is the language's own — whose comparison count is specified nowhere, varies by a factor of thirteen across input kinds, and comes within one per cent of the information floor on random input.
A distribution computed rather than sampled
Quicksort with a random pivot makes a random number of comparisons, and every plate in these essays reports one draw from that distribution. The distribution itself can be computed exactly — every pivot, every split, weighed — and on sixty-four elements its mean is 360.706 and its standard deviation 36.741. A hundred real runs average 365.98; two thousand average 360.74. The exact answer says how many runs a sample needs, and it is fewer as the input grows.
A count over every input
Run five sorts on every one of the 40,320 orderings of eight elements and read off each one's best, mean and worst comparison count. Then mark where the inputs a benchmark generator names — sorted, reversed, nearly sorted, random, few unique — land. For merge sort, heapsort and quicksort with a median-of-three pivot, the worst case is an ordering none of them produces, and for the last of the three every named input lands on its best case.
The worst case found by climbing
A search that swaps two elements at a time and keeps whatever does not lower the count finds the worst case of all five sorts at eight elements, where every answer can be checked. At sixty-four it finds merge sort's worst case every time and reaches 39% of first-element quicksort's — whose worst case is sorted input, the most famous bad input there is. Checking a search where the answer is known certifies it only there.
The sort whose count has no distribution
Batcher's network makes nineteen comparisons on every one of the 40,320 orderings of eight elements — sorted, reversed, adversarial or random — because it decides which pairs to compare before it sees any of them. That is two above merge sort's worst case and four below heapsort's best. At 65,536 elements the same refusal to adapt costs 4.07 times merge sort's worst case, and it buys three things no adaptive sort has, one of which is a proof of correctness that takes 65,536 inputs instead of twenty trillion.
The count of the part that was read
Handing back the smallest ten of 65,536 keys in order costs 965,656 comparisons by sorting them and 65,670 by a knockout tournament, against a floor of 65,526. Read to the last element, the same tournament makes exactly merge sort's 965,656 — it is merge sort, charged one element at a time. A sort's count has no term for how much of its answer anyone reads, and the two floors that do have one cannot simply be added.
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.
Two floors that can be added
Handing back the ten smallest of 65,536 keys has two floors under it and neither is close where they cross — the larger of the two is 63,821 comparisons at k = 4,000 and the best method makes 125,401. They can be added, because a comparison that eliminates a key the caller never sees can never be a comparison that orders two the caller does see. Charged together the floor rises 62%, and the tournament goes from 1.97 times it to 1.21.
The floor a merge cannot reach
Merging two sorted lists of five keys each has 252 possible outcomes, so counting says eight comparisons might do. Solving the game says nine are needed, and on equal lengths the shortfall keeps growing, as half the logarithm of the length. Averaged over random inputs, though, the same count is missed by a tenth of a comparison. The counting floor is nearly exact on average and wrong in the worst case.
The questions a sort asks twice
Selection sort makes 32,640 comparisons on 256 elements and 19,561 of them have answers it already holds. Remove every one and it still makes 7.8 times the information floor, because a question can be new and nearly worthless: insertion sort repeats nothing at all and removes 0.72 of a bit per comparison where merge sort removes 0.96. And bubble sort, less its repeats, makes exactly insertion sort's comparisons — at every size.
The price of remembering an answer
Give selection sort a table of the pairs it has already compared and it makes 16,805 comparisons on 256 elements instead of 32,640. The table pays for itself once a comparison costs more than 3.1 word operations, and that price stays near three at every size measured. Give it the full closure of everything its answers imply and it makes 13,079. The closure pays only past 425 operations a comparison at that size, and past 1,659 at twice the size. The cheap memory is worth having on long keys. The complete one is worth having almost nowhere.
The comparisons that name the answer
Returning the 4,000 smallest of 65,536 keys in order needs 61,536 comparisons to eliminate the rest and 42,100 to order the ones returned. That was the floor, 103,636, and a tournament made 125,388. What the floor never charged is saying which 4,000 come back. Charge that, and the floor is 125,341. On the same input the tournament is 47 comparisons above it, and for every k up to a hundred it is exactly on it.
The record that forgets on purpose
A table of every pair selection sort might ask is 131,072 bits at 256 elements and catches every repeated question. A direct-mapped cache of 1,024 pairs is 16,384 bits and catches 91% of them, at a break-even of 3.53 word operations a comparison against the table's 3.12. What decides the cache is not how long the sort waits before asking again — 98% of its repeats come within one pass — but how many other questions it asks meanwhile, and a model with nothing in it but collisions predicts every measured share to within 2.6%.
The spread a merge sort does not have
On 65,536 random keys quicksort's comparison count has a standard deviation of 42,470 and merge sort's has one of 141.9 — three hundred times smaller, on means only a quarter apart. Merge sort's count is a fixed bill minus 65,535 independent leftovers, one per merge, each worth about a coin toss, so its spread grows as the square root of n where quicksort's grows as n. From 256 keys up a single run of merge sort pins its mean to one per cent, and a third of quicksort's whole spread is decided by its first pivot.
The merge that can say equal
When two sorted lists draw their keys from a few values, equal keys can go on either side of each other, so far fewer answers are needed and the counting floor falls. Merging four keys into four over four values needs only 27 answers, not 70, and the floor falls from seven comparisons to five. A merge whose comparisons answer only 'at most' still needs seven on its worst input, exactly as many as distinct keys, because it can never learn that two keys are equal. A merge whose comparisons can answer 'equal' needs five and meets the floor. Solved exactly over every input, the third answer is the whole difference, and on average it is worth more than an optimal strategy.
The record measured where it would run
A table of every pair selection sort has compared saves half its comparisons at 1,024 keys, and priced in word operations it was the better record at every size. Replayed through a 32 KB cache it misses 477,824 times to save 258,290 comparisons — nearly two misses for every comparison it removes — while a cache of 1,024 pairs misses 192. The table's size is not the problem. Its layout is: it looks up and writes each question at [key][minimum], a new row every time. Indexed by the ordered pair instead, the same bits miss 3,079 times, and that repair works only for a sort whose smaller operand stays put.
A record the size of a pass's minima
Selection sort's table of every pair it has compared is 256 KB at 1,024 keys, and indexed by the ordered pair it lives almost entirely in the rows of the current minima. Keep only those rows — a ring of r rows, the least recently used given up — and 12 rows, 3 KB, catch 99% of the comparisons the whole table skips, with no misses beyond the first touch of each row. The ring beats the cache of 1,024 pairs on both axes at once. The rows it needs grow with the logarithm of the input, a few more than the minima one pass passes through, and which row it gives up matters as much as how many it has.
A record of stretches, not pairs
Selection sort asks many of its comparisons again, and a record of past answers can skip them. A table of every pair skips them all in 256 KB at 1,024 keys, and a ring of the recent minima's rows in 3 KB. The questions a pass repeats have more structure than rows record: each minimum of the previous pass was compared with one contiguous stretch of positions. Kept as a list of stretches — each minimum's position, where its stretch began, and where the key that beat it stood — the previous pass's chain answers 99.3% of what the table would, in 312 bytes. The failure predicted for it, a key the swap moves into a stretch, costs 0.04%. What the chain cannot do is stay small on every input: on reversed keys it needs a link for every key.
The runs a short list cannot have
A merge whose comparator can say 'equal' meets the counting floor on lists of repeated values, but it takes the gain only when one list's head happens to meet an equal head in the other. Comparing keys inside a list would find runs of equal keys on purpose, and was predicted to leave the worst case alone and help a great deal on average when the values are few. Solved exactly at four keys a list, it leaves the worst case alone and helps by under a hundredth of a comparison: a list of four has no run worth finding, and an equal answer already places two keys at once. On long lists the same idea, galloping over each run before comparing across again, does pay — a twenty-sixth of the textbook merge's comparisons with one value at 1,024 keys a list — and at every length it stops paying at the same place: when a value's run averages fewer than about thirty-two keys a list.
Two swaps a pass, and the stretches hold
Bidirectional selection sort finds the smallest and the largest key in one scan and places both, so a record of its past answers has to keep two chains, and each pass makes two swaps that land where the other chain reaches. The prediction was that the second swap would break stretches at a rate of whole per cent. It does not. Each chain answers its own side's repeats as the one-sided chain does — 99.1% and 99.2% at 1,024 keys — and a swap spoils about a tenth of a question whichever sort makes it, so the broken share falls as 1/n for both. What the second chain changes is the input that makes a record long: sorted keys, which the one-sided sort never repeats a question on, cost the two-ended record a link a key.
A merge that decides per run whether to gallop
Merging two sorted lists of repeated values, a merge that gallops along every equal run beats the textbook merge while the runs average more than about thirty keys a list and loses below, a rule about the whole input. A merge that learns the runs as it goes was predicted to match the better of the two on uniform values and beat both on skewed ones. The proposal's rule — gallop when the last few runs averaged long — cannot learn a run that has not ended: at one, two or four values it walks every key. Timsort's own rule, applied to equal answers — walk until a bar of consecutive equal answers, then gallop, the bar moving by one as galloping pays or fails — does what was predicted. On uniform values it stays within a hundredth of a comparison a key of the better merge; under Zipf 1, at 4,096 keys a list and 1,024 values, it makes 0.447 comparisons a key against 0.595 walking and 0.594 galloping, a quarter under both.
A run answers what nobody asked
Bidirectional selection sort remembers its past comparisons in two chains, and on sorted or reversed keys the chains need a link for every key. Keeping instead what is known about adjacent positions — which of each neighbouring pair is larger, forgotten when a swap moves either — turns a monotone stretch into a single run with a direction. On reversed keys one run replaces 1,025 links. On sorted keys the run does more than remember: it answers 260,610 questions the sort had never asked, from two keys' positions alone, and the sort makes 2,045 comparisons at 1,024 keys where the chains leave 263,167. On organ-pipe keys it cuts a quarter of the comparisons; on random keys, nothing.
A pass repaid by the scans after it
Give the two-ended selection sort one pass between neighbours before it starts, n − 1 comparisons, and sorted and reversed keys cost exactly that pass. The pass was predicted to be repaid in the first scan, and almost none of it is. On organ-pipe keys it saves 43,776 comparisons at 1,024 keys, 97% of them in the scans after the first. On random keys it costs 236, not 1,023, because later scans use the short runs it found. It breaks even on runs of four keys at every size — and the sort stays quadratic on every input that is not one run.
The runs too short to drop
A pass between neighbours leaves the two-ended selection sort a record of 674 runs on 1,024 random keys, and the scans after it use them to repay three quarters of the pass. Keeping only runs of three keys or more was predicted to cut the record by two thirds and give back under a tenth of what it repaid. It cuts the record by 63%, and gives back 69%: runs of two keys answer half of everything the record answers, because three quarters of its answers are about two neighbouring positions — the question a scan asks about the key beside the extreme it has just found. The record's cost was never in its short runs. It was in writing each run as three words: every neighbouring pair at two bits a pair is 64 words, a thirty-second of the run list, and keeps all of them.
A bar that wins rarely meet
A merge of two sorted lists of repeated values saves most of a textbook merge's comparisons by galloping along a run of equal answers once a bar of them have come in a row, with the bar lowered after a gallop that pays and raised after one that does not. Timsort keeps the same kind of bar for the other kind of stretch, one list winning repeatedly, and a merge of repeated values meets both. One count and one bar for either kind was predicted to save a further tenth under Zipf 1 and change nothing on uniform values. It saves at most 1.0% under Zipf 1, costs up to 1.3% on uniform values, and two separate bars do no better. In two lists drawn from the same distribution a stretch of wins long enough to gallop over is rare: under Zipf 1 at most 18% of the shared bar's gallops are over wins, and where wins dominate the gallops, at a thousand uniform values, the runs of either kind are too short for any gallop to pay.
What it costs to consult two bits a pair
The two-ended selection sort's record of adjacent order can be kept as two bits a neighbouring pair or as a list of runs, and the page that compared them counted both as free to read. Priced, the bits read 1.09 words a question on 1,024 random keys — under the two predicted — and a binary search of the run list takes 8.8 steps, because the pass leaves 503 runs to search. The run list was predicted to win from runs of sixteen keys; it wins only from runs of 512. Both prices are small and neither is small enough. Asked every question the sort makes, the bits spend 201 word reads for every comparison the record saves on runs of four keys, 764 at 4,096 keys, where a table of compared pairs broke even at three. The record repays its reading only on long runs, and the pass that finds them is also the cheapest place to decide whether to consult at all.
A filter that reads the word it saves
A selection sort's record of adjacent order, two bits a neighbouring pair, costs 1.09 word reads a question and spends 201 of them for every comparison it saves on 1,024 keys in short runs, because it is asked everything and answers almost nothing. A filter bit beside each pair, set only where a run could start, was predicted to turn away three quarters of the questions and cut that price to under sixty. It turns away two thirds and cuts the price to 185. The questions it turns away were already refused in the first word, the filter is read in that same word, and one read a question is a floor no filter can go under.
A run end kept in a register
A selection sort's record of adjacent order spends about a word read on every question it is asked, and on short runs it is asked 184 questions for every comparison it saves, so no filter read in that word can make it pay. Every question starts from one of the sort's two current extremes, and what the record can say about all of them is one number: where the run from that extreme ends. Kept in a register beside each extreme and refreshed only when it changes, that number cuts the reading to a forty-fifth on 1,024 keys in runs of four, and the price of a saved comparison from 201 word reads to 4.5, where it stops growing with the input.
A register dropped by what it already knew
Two registers beside a two-ended selection sort's extremes cut the reading of its record of adjacent order to a forty-fifth on short runs, and made it worse than reading the record plainly on long ones: 53.5 words a question on a sorted array of 1,024 keys against 22.1. The swaps were blamed, and the proposed repair kept the part of a broken run beyond the break as a register of its own. It changes the reading by under 1% anywhere. On the sorted array the survivors are kept 523,775 times and asked 1,022 times, and the sort makes no swap at all: every one of the 263,167 relearning drops there is a pair the record already held, rewritten at the same value by a neighbour's question that the previous scan's chains answered. The swap never broke the register. Learning what it already knew did.
A register kept through a confirmation
Two registers beside a two-ended selection sort's extremes, holding where the run of known order from each one ends, read 53.5 words a question on a sorted array of 1,024 keys, more than reading the record plainly — because 263,167 times a neighbour's question, answered by the previous scan's chains, rewrote a pair at the value it already held, and each rewrite dropped a register. Kept through such a confirmation and dropped only when a pair is forgotten or turns round, the registers read 0.347 words a question on that array, a 154th, and 0.345 on 4,096 keys: the reading stops growing with n. They become the cheapest record at every run length, 49 to 73 times under the next on runs and 5.75 times under the run list's search on the sorted array, and the price of a saved comparison now falls as runs lengthen, from 3.97 word reads at runs of four to 0.35. The dearest saving is now the short run's, and it is still above the 3.1 at which a table of compared pairs breaks even.
The request no price of memory would make
libstdc++'s stable_sort asks for a buffer of half the input. Priced in element moves against the memory held, every buffer from nothing to a buffer as large as the input has a range of memory prices at which it is the cheapest — except that one. A quarter of the input costs 1.4% more moves; a full buffer, merging out of place, saves 8% more for twice the memory; and the half-sized request sits above the line between them at every size measured. The record size, predicted to move the answer, does not: moves and memory both cost in proportion to it.
A request that reads the input first
A stable sort that asks for its buffer before it has looked at the input asks for half of it, whatever the input is. One pass to find the input's natural runs lets a merge ask only for the shorter run of each merge it will make. On input of four long runs that takes the moves from 17 a key to under 3, and on a sorted file it makes no moves at all. The buffer it needs barely falls: on anything from two runs to four thousand it asks for 36 to 45% of the input, because a balanced schedule's last merge joins two halves of the file. The request falls only where one run dominates. On a sorted file with a tenth of it appended at random, it asks for 3.7% of the input.
Named alongside it
The objects these essays reach for when they reach for this one.
Space time tradeQuicksortMerge sortPredictionSelection sortHonest limitCacheMeasured countCost modelWorst caseInformation floorLower bound