Algorithms & Data Structures
the bound is a claim, and it is checkable

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.

Every sort measured on random input, and its claim testedThe exponent fitted to each algorithm's comparison count across n from 32 to 4096, beside the class it claims. The two groups separate cleanly — nothing measures between 1.3 and 1.9 — and every claim on this input is the class that actually fits. The fitted exponent for a linearithmic algorithm sits near 1.2 rather than 1.0 because n log n is not a power law.fitted exponent of the comparison count1.01.52.0Merge sort with a cutoff1.16n log nQuicksort, median of three1.19n log nQuicksort, first-element1.21n log nMerge sort1.21n log nHeapsort1.22n log nQuicksort, random pivot1.24n log nShellsort1.25n log nInsertion sort2.00n^2Selection sort2.01n^2Bubble sort2.01n^2n from 32 to 4096comparisons, counted exactly · random input
Fig. 1 Every sorting algorithm here put through the test its complexity claim implies: the comparison count measured from n = 32 to n = 4,096 and an exponent fitted to it. The two groups separate with nothing in between, and each algorithm’s declared class is the class that actually fits. An algorithm whose claim failed would stop the build rather than be drawn with a caption it has not earned.

Start anywhere

19 essays

after 0 writes0 cmpafter 32 writes32 cmpafter 64 writes63 cmpafter 95 writes94 cmpafter 127 writes125 cmpafter 159 writes157 cmprandom input, seed stated in lib/count.js157 comparisons in this run Counting

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.

6 figures 10010³10010³10⁴10⁵10⁶ncomparisonsInsertionHeapsortMergeShellsorta power law is a straight line herecomparisons, counted exactly What a bound is

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.

6 figures every algorithm that makes at most 4 comparisonsthe 24 orderings of 4 elementsroot16 leaves16 seated · 8 with no leafone comparison per level, two outcomes per comparison⌈log₂(4!)⌉ = 5 comparisons The floors

The 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.

6 figures 10⁵10⁶10³10⁴10⁵comparisonscache misses (modelled)Insertion sortSelection sortBubble sortMerge sortHeapsortQuicksort, firstQuicksort, median-3Quicksort, randomShellsortMerge + cutofffully associative · 64 lines × 8 elements · LRUa modelled count, not a time What the machine does

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.

6 figures 110100257amortised 2.000256512append numbercost of that append (log scale)growth factor 2, cost = 1 write + a copy of the array when it resizes9 resizes in 512 appends Structures

What 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.

6 figures mean 494599th 60304,2825,4136,543comparisonsruns600 independent random inputs, n = 512worst run 1.32× the mean What is taught wrongly

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.

6 figures 10010³10010³10⁴10⁵10⁶ncomparisonsInsertionMergeHeapsortQuicksorta power law is a straight line herecomparisons, counted exactly Counting

Fitting a class to measurements

A complexity class is normally read off the shape of the loops and written down. Here it is fitted to counts taken across three orders of magnitude, and an algorithm is granted a class only if the fit holds — which turns a statement about code into a statement that can fail.

6 figures comparisons ÷ n log nMerge sort0.855Merge sort with a cutoff0.992Quicksort, random pivot1.018Quicksort, first-element1.082Quicksort, median of three1.117Shellsort1.246Heapsort1.649all of these fit n log n1.9× between best and worst What a bound is

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.

6 figures the floorMerge sort1.02×Quicksort, first1.23×Quicksort, random1.24×Merge sort + cutoff1.29×Quicksort, median-31.32×Shellsort1.45×Heapsort1.96×Insertion sort9.69×Bubble sort19.26×Selection sort19.38×floor = log₂(256!) = 1,684 comparisonsmean of 16 runs, against a proved bound The floors

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.

6 figures 0%25%50%75%100%645124,09665,536cache holds 512array size n (elements)miss ratefully associative · 64 lines × 8 elements · LRU20,000 random accesses per point What the machine does

The cliff where the data stops fitting

Below the cache's capacity, almost every access hits. A factor of eight above it, almost every access misses. The transition is not gradual and it is not a property of any algorithm — it is a property of how much data there is, and an algorithm's complexity class says nothing about which side of it a program is working on.

6 figures 0%25%50%75%12345×1.125×1.25×1.5×2×3×4capacity left unused at the endamortised cost per append20,000 appends, cost = 1 write + a copy on resizeneither end wins Structures

Choosing a growth factor

When a dynamic array fills up, how much bigger should the new one be? Doubling costs 2.02 units per append and leaves 39% of the allocation empty. Growing by an eighth costs 9.89 and leaves 10%. Every factor is a trade between time and space, no factor wins on both, and real implementations disagree about the answer for reasons that are measurable.

6 figures first-element pivot130,816 on sortedmedian of three5088 meanrandom pivot4937 meanblue bar: range over 400 random inputs · marker: the already-sorted inputn = 512a bad case that cannot be chosen is a different kind of bad case What is taught wrongly

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.

7 figures comparisonsswapsInsertion sort63,071 / 0Selection sort130,816 / 504Bubble sort129,688 / 62,563Merge sort3,964 / 0Heapsort7,653 / 4,170Quicksort5,049 / 2,380n = 512, random inputcounted in the same run Counting

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.

7 figures -50%-40%-30%-20%-10%0%10%20%2561,0244,09616,384α = 0.5α = 0.8α = 0.9α = 0.95table size (slots)measured minus formula, relativemean of 6 fills per pointgreen band: within 5% of the formula What a bound is

A limit is not a prediction

Measured from n = 64 to n = 4,096, this site's hybrid merge sort fits a linear class better than n log n. Measured out to n = 65,536, the ranking reverses. Nothing changed but the range — and this is not a flaw in the method, it is the method finding the exact place where measurement stops being able to help.

6 figures comparisons (bar length is log-scaled)sorting, floor43,250sorting, merge sort43,976searching, floor13searching, binary13searching, linear4,096green outline: a proved floor · blue: a measured run3,327× between the two floors The floors

The floor moves when the question does

Sorting 4,096 elements needs at least 43,250 comparisons. Finding one element among the same 4,096, already sorted, needs at least 13. The difference is a factor of 3,300 and it comes entirely from how many different answers the algorithm has to be able to give. A lower bound is a property of the question, not of any algorithm.

6 figures Merge sort49% sequential · 7,540 accesses2560Heapsort15% sequential · 14,044 accesses2560time (accesses, left to right) · index (bottom to top)one run each, n = 256every access plotted What the machine does

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).

6 figures sorted insertion — height 62shuffled insertion — height 10truncated at depth 1663 keys, identical set, different arrival order62 deep against 10 Structures

The tree that is a list

A binary search tree gives logarithmic lookup. Build one from 128 keys in sorted order and it has height 127 — every node has one child, and a lookup is a linear scan. The failure is not gradual and it happens on the input people try first, which makes "O(log n) lookup" a claim about the insertion order rather than about the structure.

6 figures 1234560.000.250.500.75formulameasuredload factor αprobes per insertion8,192 slots, mean of 8 fills, seeds stated in lib/structures.jstwo routes agree to 2.3% What is taught wrongly

The probe formula nobody checks

The expected number of probes to insert into a hash table under linear probing is ½(1 + 1/(1−α)²). It is quoted constantly, it is correct, and applied to a table of 256 slots at 95% load it overstates the measured cost by nearly half — because it is an asymptotic result and a real table is not asymptotic.

6 figures 481632641281010010³10⁴noperations (mean of 60 runs)Insertion trafficMerge trafficInsertion cmpMerge cmptraffic crossessolid: reads + writes · dashed: comparisonstraffic crosses between n = 12 and 16; comparisons never do What the machine does

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.

6 figures

Threads running through

themes, not chapters

Measured, not asserted

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.

15 essays

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.

4 essays

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.

5 essays

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.

3 essays

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.

3 essays

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.

3 essays

A limit is not a prediction

An asymptotic bound describes behaviour as n grows without end. It does not say which of two algorithms is faster at the size anyone will actually run, and treating it as though it does is the commonest error in the subject.

5 essays