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

Counting convention — where it appears

The stated rule for which operations a count charges and which it ignores, such as comparisons but not swaps, or reads but not writes. Two counts of one run under different conventions can rank the same algorithms in opposite orders.

Named by 5 essays across one field — each of them below, with the objects they name alongside it.

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

Two pivots and what they cost

Java changed its primitive sort in 2011 on the strength of an analysis showing dual-pivot quicksort does fewer comparisons than the classical one. It does. It also does nearly twice the swaps, and the analysis that decided the matter counted neither — it counted a weighted combination that had to be chosen before any conclusion could be drawn.

counting · Count 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 network makes nineteen comparisons on every one of the 40,320 orderings of eight elements — sorted, reversed, adversarial or random — because it decides which pairs to compare before it sees any of them. That is two above merge sort's worst case and four below heapsort's best. At 65,536 elements the same refusal to adapt costs 4.07 times merge sort's worst case, and it buys three things no adaptive sort has, one of which is a proof of correctness that takes 65,536 inputs instead of twenty trillion.

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

Four of the eight sorts here leave every pair of equal keys in the order it arrived in and four move between 1,209 and 2,403 pairs, and none of the four counts every plate here reports can tell them apart. Decorating each record with its arrival position makes any of them stable, for four thousand words and between 0.05 and 1.64 times its comparisons — a charge of 64% on Shellsort and a saving of 95% on quicksort, because the ties stability has to break are the ties a two-way partition chokes on.

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

Every count on this collection is a count of comparisons, swaps, reads or writes, and radix sort makes zero of the first. On 65,536 keys it moves five times less data than merge sort, misses the cache three times more, and sits 954,037 comparisons under the floor no comparison sort can go beneath — which is not an achievement, because the floor was never a statement about it.

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

Selection sort makes 32,640 comparisons on 256 elements and 19,561 of them have answers it already holds. Remove every one and it still makes 7.8 times the information floor, because a question can be new and nearly worthless: insertion sort repeats nothing at all and removes 0.72 of a bit per comparison where merge sort removes 0.96. And bubble sort, less its repeats, makes exactly insertion sort's comparisons — at every size.

counting · Count

Named alongside it

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

Comparison countInformation floorMeasurement designMerge sortLower boundQuicksortSpace time tradeSpecificationStabilitySwapsThree-way partitionBranchless

All concepts