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

Counting sort — where it appears

A sort that tallies occurrences of each key value and reads them out in order, avoiding comparisons entirely at the cost of a bounded universe. It avoids comparisons entirely at the cost of a bounded universe, which puts it outside the comparison-sorting floor rather than under it.

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

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

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

floors · Floor pale: total slots ever allocated · dark: peak held at onceone buffer, allocated once16,38416,400peak 100% of na buffer per merge229,37616,386peak 100% of nn = 16,384, random input208,687 comparisons each — identical in time

The space the model does not see

A slot is not a byte, a frame is not a slot, sixteen thousand allocations are not one allocation of the same size, and none of these numbers includes the input. The space counters are the newest instrument here and the honest account of what they miss is longer than the account of what they measure — including one bound this phase set out to demonstrate and could not.

space · Space the floor that applieslog₂(n!)Merge sort2.3×1,682Shellsort2.3×1,714Merge sort + cutoff2.6×1,938Heapsort4.2×3,101Quicksort, first6.6×4,887Quicksort, random7.2×5,291Quicksort, median-37.8×5,728Insertion sort18.5×13,644Bubble sort43.1×31,820Selection sort44.2×32,6408 distinct values, n = 256, seededthe two floors are 2.28× apart

The floor when the values repeat

log₂(n!) counts orderings of distinguishable things. Two hundred and fifty-six values drawn from eight distinct ones have 1,684 bits of permutation entropy and 739 bits of distinguishability, so the real floor is less than half the one every table quotes — and merge sort, which sits exactly on the quoted floor, is 2.3 times above the one that applies.

floors · Floor

Named alongside it

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

Lower boundCacheComparison countInformation theoryQuicksortStirling's approximationAccess patternAllocatorAuxiliary spaceBinary searchBranching programComplexity class

All concepts