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

Counting

Comparisons, swaps, reads and writes are exactly countable and machine-independent. Every claim on this site starts by counting rather than by reading the code.
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 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.

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

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.

 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

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.

 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

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.

 10³10⁴10³10⁴10⁵nrandom bitsskip list, one build — ntreap, one build — nreservoir, Algorithm R — n log nn from 256 to 16,384bits charged including rejections

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.

 Dual-pivot116,836shipsIntrosort130,863shipspdqsort114,408shipsTimsort95,770shipsalgorithmcomparisonsrandom, n = 8,192comparisons, counted exactly

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.

 4 bytes32 bytes128 bytes512 bytesrecord:QuicksortMerge sortShellsortHeapsortInsertion sortSelection sortBubble sortQuicksortShellsortMerge sortHeapsortSelection sortInsertion sortBubble sortQuicksortShellsortMerge sortSelection sortHeapsortInsertion sortBubble sortSelection sortQuicksortShellsortMerge sortHeapsortInsertion sortBubble sort1234567n = 512, random input, key 8 bytesa read or a write moves the record; a comparison touches the key

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 language's sortMerge sortlog₂(n!)random43,810 / 43,976nearly sorted10,806 / 24,845already sorted4,095 / 24,576reversed4,095 / 24,576few distinct values27,561 / 42,338n = 4,096, counted through the comparatorthe first column is a fact about the engine, not about sorting

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.

 0.0000.0100.0200.030150200comparisonsprobability per comparison countmean 139.86exact400 runsn = 32, pivot chosen uniformlysampled mean 140.19

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.

 every orderthe named inputsmean0102030comparisonsInsertion sort7 to 28 · named inputs reach 28Merge sort12 to 17 · named inputs reach 16Heapsort21 to 29 · named inputs reach 27Quicksort, first-element pivot13 to 28 · named inputs reach 28Quicksort, median of three25 to 29 · named inputs reach 2540,320 orders of 8 distinct elements3 worst cases unnamed

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.

 40%60%80%100%8121624324864elements sortedshare of the known worst case the climbs reach, on averageInsertion sort · 20 of 24Merge sort · 24 of 24First-element quicksort · 0 of 24hollow: none reached it24 climbs a size · 100 swaps per elementworst cases known 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.

 0.0010.010.11125102050fraction of positions reshuffled, pmean comparisons, in multiples of the mean on random inputFirst-element quicksort, 81.9×Median-of-three quicksort, 41.4×Insertion sort, 2.0×Merge sort, 1.0××: unshuffled2,048 elements · 12 shuffles a point1 = the mean on random input

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.

 0102030comparisons on one orderingfloor 16Insertion sort7 to 28 · mean 19.28Merge sort12 to 17 · mean 15.73Heapsort21 to 29 · mean 25.81First-element quicksort13 to 28 · mean 16.92Median-of-three quicksort25 to 29 · mean 26.30Batcher's network19 on all 40,32040,320 orders of 8, enumeratedfloor ⌈log₂ 8!⌉ = 16

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.

 1101001,00010,00010⁵10⁶k, the elements the caller readscomparisonssort all, read kbuild a heap, pop kselect k, sort thoseincremental quicksortkeep the best k while scanningknockout tournamentdashed: the floorlabels at k = 1,00065,536 random distinct keysevery answer checked

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.

 Merge sortnone · 55% tiesMerge sort with an insertion cutoffnone · 47% tiesInsertion sortnone · 0% tiesBubble sortnone · 55% tiesShellsort2,014 · 71% tiesHeapsort2,403 · 32% tiesSelection sort1,209 · 24% tiesQuicksort, median-of-three pivot1,428 · 99% tiesequal pairs left out of the order they arrived in4,096 records, 8 distinct keysdark: the sorts that move them

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.

 reads and writescache missesRadix sort, 8-bit digitsno comparisonsMerge sort965,752 comparisonsHeapsort1,895,405 comparisonsQuicksort, median-of-three1,187,435 comparisons65,536 keys of 32 bitsdark: the sort that compares nothing

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.

 1416642561k2k4k8k16k33k66k11010010³10⁴10⁵10⁶keys handed backcomparisons no method can go underthe losers, and the outputs' ownorderevery element not handed back losesthe answer is one of n!/(n−k)!sequences65,536 keyseach is a claim about every possible method

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.

 0%25%50%75%Merge sort0.0% · 1.03× the floorQuicksort, random pivot0.0% · 1.16× the floorQuicksort, first-element pivot0.0% · 1.18× the floorMerge sort with an insertion cutoff0.0% · 1.31× the floorInsertion sort0.0% · 9.83× the floorShellsort9.8% · 1.31× the floorQuicksort, median-of-three15.4% · 1.18× the floorHeapsort26.2% · 1.45× the floorBubble sort49.2% · 9.83× the floorSelection sort59.9% · 7.77× the floorshare of comparisons whose answer was already implied256 elements, random orderlight: repeats nothing

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.

 32641282565121010010³10⁴elements sortedword operations a comparison must cost to break evenSelection sort, pairsSelection sort, closureBubble sort, pairsBubble sort, closureHeapsort, pairsHeapsort, closureQuicksort, median-of-three, pairsQuicksort, median-of-three, closuresolid: pairs asked · dashed: everything impliedrandom input · counted exactly

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.

 11010010³10⁴10⁵10⁶k, the number handed backcomparisonstournament, measuredfloor that names the outputsbest earlier floorn = 65,536, one shuffled inputthe floors are worst-case, the count is one input

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.

All essays