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

Recursion depth — where it appears

How many frames a recursive procedure holds at once, which is auxiliary space that no array counter sees and that a real stack can exhaust. It is auxiliary space no array counter sees, and it is what a real stack exhausts — a limit measured here rather than assumed away.

Named by 6 essays across 4 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 10010³1010010³nstack framesa stack of 512 framespivot: first-elementpivot: median of threepivot: random pivotMerge sortalready sorted input, n from 64 to 4,096one frame charged as one slot

The stack nobody counts

Merge sort makes 8,192 calls to sort 4,096 elements and holds fourteen of them at once. Depth-first search on a grid holds twelve vertices, or sixty-six, or a hundred and forty-four, depending on which of three equally standard implementations is running. The stack is a resource, it is the one that fails hard rather than slowly, and nothing that watches the data can see it.

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 algorithmspread of count ⁄ f(n) — 1.0 is exactTimsortPython, Java objects, Rust, Android1.176nIntrosortC++ std::sort1.104n log nPattern-defeating quicksortRust unstable sort, Boost, libstdc++ 141.155nDual-pivot quicksortJava Arrays.sort, primitives1.624no class grantedtolerance 1.6fitted n = 256–16,384comparisons, counted exactly

The pattern that defeats the pattern

Quicksort's bad cases are patterns — sorted input, organ-pipe input, an adversary's construction. Introsort's answer is to notice the damage and switch algorithms. pdqsort's answer is to notice the pattern and break it, deterministically, with four swaps. On input with eight distinct values that turns a quadratic disaster into a linear sort, and the whole difference is one extra partition scheme.

practice · Practice 10³10³10⁴10⁵10⁶10⁷ncomparisonsadversary, no depth limitadversary, as it shipsrandom inputn²/2McIlroy's adversary, answering as it goescomparisons, counted exactly

The depth limit that almost never fires

Introsort counts how deep its recursion has gone and calls heapsort if it passes twice the logarithm. On every input measured, the mechanism handles under a tenth of a per cent of the elements. Then an adversary that answers the comparisons rather than choosing the array drives it to exactly n²/2 with the limit removed, and to one heapsort call with it — a factor of forty-two at n = 8,192, and growing.

bounds · Bound 1,00010,00010phrases followed12481632characters in the collection · copies aboveworst depthmean depthEnglish-like · z = 156median 18 · 90th 31

The character that costs a chain

The index over thirty-two copies is 8,892 bits and does not grow. Producing one character of the text it indexes costs 17.89 phrase-follows on average and 38 in the worst case, against 2.38 and 7 at one copy — the size stopped growing and the price of reading it did not.

space · Parse

Named alongside it

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

QuicksortPartitionPivotAuxiliary spaceGuaranteePeak and totalDepth limitIn placeIntrosortpdqsortTraversalAdjacency

All concepts