Counting
Counting instead of timing
Why every measurement on this site is an exact operation count rather than a duration, what the instrumented array counts and what it deliberately does not, and the check that refuses to measure an algorithm that did not work.
Fitting a class to measurements
How a complexity class is fitted to measured operation counts, why the ratio test beats a slope on log–log axes, what tolerance separates a real fit from a wrong one, and the two claims on this site that the fit refused to grant.
One run, four counts, four answers
Why comparisons, swaps, reads and writes rank the same algorithms in different orders, what each count is actually good for, and how the choice of cost model quietly decides the answer to every comparison anyone makes.
The count somebody chose
Six countable quantities, six rankings, and how far apart they are — with the pairwise disagreements measured, and what a cost model is once it is written down as the weighting it always was.
Counting the coin flips
Randomness as a measured resource beside comparisons, cache misses and slots — how it is charged, what each randomised algorithm here consumes, and the one class the site's vocabulary could not grant.
Two pivots and what they cost
Dual-pivot quicksort measured on four counters, none of which agrees with the others, and what it means that an algorithm was adopted on the strength of a weighting.
The exchange rate nobody wrote down
The record size as an explicit exchange rate between the counts this site takes, where each pair of sorts changes places, and the one case where the model can be checked and is wrong.
The count that came from somewhere else
An audit of this collection's own reproducibility claim, the two measurements that pass through an unspecified routine, and what counting its comparisons reveals about it.
A distribution computed rather than sampled
Quicksort's comparison count as an exact probability distribution, computed by convolving its recurrence, laid over histograms of real runs. The exact moments say how many runs a sampled mean needs for a stated precision — 793 for one per cent at sixteen elements, 85 at four thousand — because the spread grows more slowly than the mean.
A count over every input
Five sorts run on every permutation of eight elements, with the inputs a benchmark generator names marked among them. Three of the five have worst cases no named input reaches, one has every named input at its best case, and first-element quicksort's average over every input equals randomised quicksort's expected count exactly.
The worst case found by climbing
A local search for worst-case inputs, validated against exhaustive enumeration at eight elements and then run where enumeration cannot reach. It reaches merge sort's exact worst case at every size, stalls on a plateau at about half of first-element quicksort's, loses to McIlroy's adversary on the quicksorts and to nothing on heapsort, where no worst case is known.
A worst case ten positions wide
Each sort's worst-case input with a fraction of its positions reshuffled. First-element quicksort's sorted input loses half its cost to about ten reshuffled positions at every size measured, while insertion sort's reversed input keeps 71% at half reshuffled, exactly as a count of inverted pairs predicts. At eight elements, the number of orderings that reach each sort's worst case runs from 128 to 10,240.
The sort whose count has no distribution
Batcher's odd–even merge sort network measured against the adaptive sorts. Its comparison count is fixed by n alone, sitting between merge sort's worst and heapsort's best at eight elements and growing to four times merge sort's worst at 65,536; its exchanges still vary; and the zero–one principle lets every input of sixteen be checked in 65,536 runs, with each of its 63 comparators shown to be necessary.
The count of the part that was read
Six ways to return the k smallest of n keys in order, counted against k from one to all of them, with two floors — one from elements that must lose, one from information — and the demonstration that their sum is not a floor. A knockout tournament stays near the floor wherever the floor is tight and, read to the end, makes exactly merge sort's comparisons.
The order equal keys keep
Stability measured rather than quoted: which sorts keep equal keys in order, how many pairs the others move, what the tie share is as the distinct keys vary, and what decorating each record with its position costs each sort in comparisons and in space.
The sort that makes none of them
Radix sort counted in the same four primitives as every comparison sort here: no comparisons at any digit width, reads and writes set by the key's width rather than by the number of orderings, and a cache miss rate that is the reason it is not the answer.
Two floors that can be added
A third floor under returning the k smallest in order — the elements that must lose, plus the comparisons the outputs' own order needs — proved disjoint, computed at every k, and checked against the exact optimum found by minimax at sizes where it can be computed.
The questions a sort asks twice
Every comparison a sort makes, checked against the transitive closure of the comparisons before it, and every comparison priced in the orderings it actually eliminated — counted exactly as linear extensions of the partial order the sort has built.
The price of remembering an answer
Six sorts given two records of what they have learned — the pairs already compared, and the transitive closure of every answer — with the record's lookups and upkeep counted in word operations beside the comparisons it saves. The break-even price of a comparison at sizes from 32 to 512, the cost as that price rises, and the inputs on which either record has anything to remove.
The comparisons that name the answer
A third term for the floor under returning the k smallest in order: the bits needed to name the first k − 1 outputs, on top of the n − k eliminations. Checked against the exact optimum found by solving over every partial order of up to six elements, split into its parts at two sizes, and set against a tournament, a heap and a selection that sorts afterwards at k from 1 to 65,536.
The record that forgets on purpose
A fixed-size direct-mapped cache of recently asked comparisons, placed between no record at all and a table of every pair: the gap distribution of each sort's repeated questions, what a cache of each size catches against a collision model, the state-against-price trade, and where the curve goes flat.
The spread a merge sort does not have
The exact distribution of top-down merge sort's comparison count on random input, by convolving the leftover of every merge: its spread against quicksort's, where in the recursion each sort's spread is made, its shape, the runs a benchmark needs, the periodic wobble in its variance, and the sliver of the worst-case range it actually uses.
The record measured where it would run
Selection sort's records of past comparisons — none, a direct-mapped cache of 1,024 pairs, the table of every pair as written, and the same table indexed by the ordered pair — with every array and record access replayed through an exact LRU cache of 64-byte lines: misses against size and against capacity, comparisons saved per miss, the same records under bubble, insertion and merge sort, and the first pass drawn in the table.
The digit a pass chooses for itself
A least-significant-digit radix sort of 65,536 keys with its counters and its scattered writes in the trace, through exact LRU caches of 32 KB and 256 KB: misses a key against digit width on four kinds of key, the fields a plan chooses from one pre-pass of byte histograms and a sample, every case against every fixed width, and each rule's worst regret.
A record the size of a pass's minima
Selection sort on random keys with a record of past comparisons made of a few rows of the ordered table of pairs — one row for each recent minimum, least recently used given up — replayed through an exact LRU cache of 64-byte lines: the share of the full table's skipped comparisons caught against the number of rows at three sizes, which keys a pass's minima are pass by pass, comparisons skipped against misses for every record, the rows needed as the input grows, and two rules for choosing the row to give up.
A record of stretches, not pairs
Selection sort with a record made of the previous pass's chain of minima — each minimum's position and the stretch of positions scanned while it was current, ending with the key that beat it — on random keys from 128 to 4,096 and on reversed, organ-pipe and sorted orderings, every answer the record gives checked against the keys: one pass's chain and the next pass's questions it answers, the share of the full table's skips it catches beside a ring of twelve rows, the record's size, what it misses and why, and four orderings.
Two swaps a pass, and the stretches hold
Bidirectional selection sort with a record of the previous pass's chain of minima and chain of maxima, each link a position and the stretch of positions compared with it while it was current, on random keys from 128 to 4,096 and on reversed, organ-pipe and sorted orderings, every answer checked against the keys: one pass's two chains, each chain's catch of its own side's repeats beside the one-sided sort's chain, the questions a swap breaks and which swap breaks them, the links held, and four orderings.
A run answers what nobody asked
Bidirectional selection sort on random, reversed, organ-pipe and sorted orderings of 128 to 4,096 keys, with three records of its past comparisons — the previous pass's two chains of minima and maxima, the runs of adjacent positions whose order is known, and both — every answer checked against the keys and every answer to a question never asked counted apart: comparisons made on sorted keys against n, comparisons made on each ordering, what each record holds, the organ-pipe case divided between repeats and questions never asked, and random keys, where runs add nothing.
A pass repaid by the scans after it
Bidirectional selection sort keeping the previous pass's two chains and the runs of neighbouring positions of known order, with and without a first pass of n − 1 comparisons between neighbours, on random, reversed, organ-pipe and sorted keys and on inputs of equal sorted runs, 256 to 4,096 keys, every answer checked against the keys: the comparisons on the four orderings, where the pass's cost goes on random keys, the comparisons of every pass on organ-pipe keys, the change a key against the length of the input's runs, and the size of the record the pass leaves behind.
The runs too short to drop
Bidirectional selection sort with the previous pass's two chains and a record of runs of neighbouring positions of known order, after a first pass of n − 1 comparisons between neighbours, keeping only runs of at least 2, 3, 4, 5 or 8 keys, on random keys at 256, 1,024 and 4,096 and on inputs of equal sorted runs of 4, 8 and 16 keys, every answer checked against the keys: the comparisons the pass adds against the shortest run kept; the record's largest size in words beside a record of two bits a pair; questions answered by the length of the run that answered them; the share of answers about neighbouring positions; the cost of dropping short runs on inputs of long ones; and comparisons against words.