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

In place — where it appears

A claim that a procedure uses no auxiliary space beyond a constant, which for a recursive sort is usually false by a logarithm. For a recursive sort it is usually false by a logarithm, which is a factor the phrase conceals and a stack depth makes visible.

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

peak slots held at once, logarithmic18645124096Insertion sort11Selection sort11Bubble sort11Heapsort11Shellsort11Quicksort, median of three22log nQuicksort, random pivot28log nQuicksort, first-element29log nMerge sort with a cutoff4,106nMerge sort4,110nn = 4,096, random inputone slot = one array element or one stack frame

Measuring what an algorithm keeps

Four counters measure what an algorithm does and none of them measures what it holds. An in-place sort and an out-of-place one with identical comparison counts are different algorithms, and until this phase the site had no way to say so. Two primitives close the gap, and the second of them counts something no array counter can ever see.

space · Space peak slots held at once, logarithmic18645124096Insertion sort11Selection sort11Bubble sort11Heapsort11Shellsort11Quicksort, median of three14log nQuicksort, random pivot32log nQuicksort, first-element4,097nMerge sort with a cutoff4,106nMerge sort4,110nn = 4,096, already sorted inputone slot = one array element or one stack frame

In place is a claim, and it is usually wrong about quicksort

Heapsort holds one slot at its peak. Quicksort holds twenty-two at n = 4,096 on random input and 4,097 on a sorted one. Merge sort holds 4,110. All three are described with the same two words, one of the three descriptions is false, and the false one is the algorithm the phrase is most often attached to.

wrong · Space 2,0484,0968,1921010010³10⁴nleast fast memory, cellsheapsortShellsortquicksort, random pivotquicksort, median of threefamily, 16 cellsfamily, 64 cellsfamily, 256 cellswithin 8 × n²/Bdoubling grid of memories

The memory a product does not charge

Time times space charges a sort for the cells it writes and not for the fast memory it needs to write them cheaply. Counted three ways, on random keys in lines of eight, a read-only family stays within a factor of eight of the floor with 32 to 256 cells of fast memory at every length, while heapsort needs all of n and quicksort an eighth of it. Quicksort's need falls far faster than predicted as the factor loosens. And the product the floor leaves out, transfers times fast memory, separates the two kinds of sort completely: no read-only sort can push it far below n²/B, and quicksort reaches a twentieth of it.

bounds · Bound 1664256102440961210100fast memory M, cellstransfers × writable cells, per n²/Btwo: one read, one write of nheapsortShellsortquicksort, random pivotfamily, 16 cellsfamily, 64 cellsfamily, 256 cellsn = 8,192, write-backs chargedthe floor at one

The lines a sort writes back

A replay that charges a transfer for every line brought into fast memory and none for a line sent back flatters every sort that writes in place. Charged for its write-backs, quicksort's transfers rise by 1.9 at every memory short of n, as predicted, and heapsort's by 1.8, not the predicted three, because no line can go back more often than it came in. The cost that changes the account is the last one: at n itself every in-place sort pays two reads of its array, so none of them can come within a factor of two of the floor, while the read-only family reaches 1.07.

bounds · Bound

Named alongside it

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

Cost modelAuxiliary spaceBlock transferExternal-memoryLocalityLower boundQuicksortRecursion depthTime space tradeoffWorking setAllocatorComparison count

All concepts