Insertion sort never beats merge sort on comparisons — not even at four elements.
Every standard library 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: at every size from four elements upwards it does more. The crossover is real and it is entirely in memory traffic — merge sort reads and writes a buffer and copies it back, and below about a dozen elements that costs more than insertion sort's extra comparisons. One count says the fallback is pointless and the other says it is necessary. These are essays about algorithms with the operations counted rather than described.
384 essays · 15 fields · 31 ladders · 154 generators · twelve counted resources
Comparisons and swaps, cache misses, auxiliary space and recursion depth, random bits, block transfers, characters, bits of retained state, subproblems held, bits of index, the timestamps a structure needs in order to forget, and the characters an algorithm managed not to read. Every essay names which of them it is counting, and no claim on this site is made in a unit nothing measures.
Start anywhere
one essay from each of the 15 fields · 384 in all
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.
CountingCounting 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 floorsThe floor under every comparison sort
No algorithm that sorts by comparing pairs of elements can average fewer than log₂(n!) comparisons. Not one that exists, and not one that ever will. The argument takes three sentences, it is about counting leaves in a tree, and it is one of the few results in this subject that is genuinely about every possible algorithm rather than about a particular one.
What the machine doesThe 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.
StructuresWhat amortised means
Appending to a dynamic array is O(1) amortised. It is also, on 512 appends, an operation that costs one unit 503 times and 257 units once. The amortised bound is a true statement about the sequence and a false one about any append in it, and the picture that shows why is a sawtooth nobody draws.
Two parametersCounting on a graph
An instrumented array counts comparisons, swaps, reads and writes, and none of those is what a graph algorithm spends its time on. Three new primitives are needed — an adjacency scanned, a vertex first reached, an edge relaxed — and once they exist, breadth-first and depth-first search turn out to be the same algorithm by every count kept on arrays.
The other axisMeasuring what an algorithm keeps
Four counters measure what an algorithm does and none of them measures what it holds. An in-place sort and an out-of-place one with identical comparison counts are different algorithms, and until this phase the site had no way to say so. Two primitives close the gap, and the second of them counts something no array counter can ever see.
When the algorithm flips a coinA 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.
What the libraries doThe 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.
When it does not fitOne access, eight kilobytes
Every count on this site charges one for an array access. A machine charges for a block. The same 65,536 accesses cost 1,024 transfers in one order and 65,536 in another, with nothing about the algorithm's work changed — a factor of 64, which is exactly the number of elements in a block, and which no counter here could see until now.
One pass, and no roomThe answer that is allowed to be wrong
Every algorithm on this site so far was checked for correctness before it was measured. A summary of a stream cannot be — the data goes past once and does not fit — so the error becomes a resource, bought with bits, at an exchange rate that is a measurement.
The data that is not a numberThe comparison that is not one comparison
Sorting 512 keys costs 3,955 comparisons whatever the keys are, and between 7,849 and 134,409 character examinations depending only on how much those keys have in common. The first number is the one every bound so far is stated in. The second is the one the machine pays, it grows without limit, and nothing here has ever counted it.
When the algorithm is a tableThe 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 index that replaces the textAn index larger than what it indexes
A suffix array over 16,384 characters is 229,376 bits, and it cannot answer a single question without the 81,920 bits of text beside it. Nearly four times the text, to search the text. Every index on this site had been weighed at zero until somebody put one on a scale.
What is taught wronglyThe 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.
All 384 essays · The 15 fields · Every ladder
Or follow one idea down
the deepest ladders · all 31
Distance — 29 rungs Symbol — 27 rungs Parse — 23 rungs Transfer — 23 rungs Graph — 22 rungs Count — 21 rungs Index — 21 rungs Document — 20 rungs Randomness — 19 rungs Machine — 14 rungs
Threads running through
themes, not chapters · all 36
Measured, not assumed
A complexity class is usually read off the shape of the loops. Here it is fitted to counts taken across three orders of magnitude, and an algorithm is not given a class until the fit holds.
The constant is the content
Three sorts are all Θ(n log n) and their measured comparison counts differ by a factor of three. The class is what they have in common; the constant is what distinguishes them, and it is the part that gets dropped.
Two counts, two rankings
Comparisons are what textbooks count and cache misses are what the clock feels. They are independent, they rank algorithms differently, and the gap between them is where the practical knowledge lives.
There is a floor
Comparison sorting cannot use fewer than log₂(n!) comparisons, and that number is computable exactly. The distance between an algorithm and the floor is a measurement rather than a feeling.
Distributions, not averages
The expected cost of a randomised algorithm is the least interesting thing about it. What matters is how tightly the distribution concentrates, and that is what makes the bad cases stop mattering.
The figure is the run
Every trace here is a real execution and every number in its caption came from that same execution. A picture and its counts cannot disagree, because there is only one of them.