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

Benchmarking — where it appears

Measuring a run under a stated input and a stated model, whose numbers describe that setting and do not transfer to another. Its numbers describe the setting they were taken in and do not transfer to another, which is why the input and the model are stated beside every one.

Named by 6 essays across 4 fields — each of them below, with the objects they name alongside it.

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

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.

counting · Count 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

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.

floors · Floor 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

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.

counting · Count 1,00010,00010³10⁴characters of textcomparisons, built and scannedcrossing at n = 32,000both rules, exactlythe 1979 tables2 patterns of 10 · four symbolscrossing n = 32,000

The rule that pays on a long enough text

With two patterns, the cheap tables cost 106 steps and the scan reads 13,084 characters; the exact tables cost 594 and the scan reads 12,306. Below thirty-two thousand characters the cheap tables win the total, above it the extra skipping pays for them, and with thirty-two patterns there is no crossing at all.

practice · Symbol 1,00010,00010³10⁴characters of textsteps, precomputation plus scancrossing at 8,000published rulesexact rules2 patterns · four symbolscrossing 8,000 · was 32,000

Where the exact rules pay now

With a construction as cheap as the published one, the exact shift rules pay for themselves past eight thousand characters of text at two patterns, four thousand at four, and never at thirty-two — because by thirty-two patterns the two rules make identical decisions.

practice · Symbol 01002003004005006007008009001000roundloads 1.0×blockedloads 1.0×hashedloads 17.6×worst error over the heaviest keyschaintreesmallest-firstlargest-first32 shards · k = 32 · 40,000 arrivalseven 1.00× · uneven 2.7×

A parameter that waits for another

Four merge fold shapes over thirty-two evenly loaded shards leave errors of 665, 667, 665 and 667 — a fifth of a per cent apart. Give the same four shapes shards whose loads span seventeen-fold and they leave 148, 183, 323 and 403. The parameter did nothing until a second parameter moved, and every measurement that fixed the second one saw nothing.

wrong · Merge

Named alongside it

The objects these essays reach for when they reach for this one.

Comparison countMeasurementParameter choiceTrade offCommentz-walterCounterexampleCrossoverDistributionMulti patternOperation countPreprocessingQuicksort

All concepts