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

Comparisons against peak auxiliary space, n = 8,192

Rendered here at the parameters it defaults to, with every essay that calls it — which is the same list as the blast radius of changing it.
Comparisons against peak auxiliary space, n = 8,192One point per sort, both axes logarithmic, cheapest and smallest towards the bottom left. The line joins the Pareto frontier — the 5 algorithms that nothing else beats on both counts at once. The 5 points off it are dominated, and being dominated is a stronger statement than being slower: there is no weighting of these two costs under which they are the right choice. This is the honest answer to "which sorting algorithm", and it is a shape rather than a name.10⁵10⁶10⁷11010010³10⁴comparisonspeak auxiliary slotsInsertion sortSelection sortBubble sortMerge sortHeapsortQuicksortQuicksortQuicksortShellsortMerge sort with a cutoffn = 8,192, random input5 on the frontier, 5 dominated

Comparisons against peak auxiliary space, n = 8,192

One point per sort, both axes logarithmic, cheapest and smallest towards the bottom left. The line joins the Pareto frontier — the 5 algorithms that nothing else beats on both counts at once. The 5 points off it are dominated, and being dominated is a stronger statement than being slower: there is no weighting of these two costs under which they are the right choice. This is the honest answer to "which sorting algorithm", and it is a shape rather than a name.

Drawn at 700 × 430, wide on the page. Everything above is what time-space-frontier returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

9 essays call time-space-frontier. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.

Where it is called

Changing this generator changes every one of these figures.

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 The other axis

Measuring what an algorithm keeps

 10⁵10⁶10⁷11010010³10⁴comparisonspeak auxiliary slotsInsertion sortSelection sortBubble sortMerge sortHeapsortQuicksortQuicksortQuicksortShellsortMerge sort with a cutoffn = 8,192, random input5 on the frontier, 5 dominated The other axis

The frontier between time and 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 What is taught wrongly

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

 11010010⁴10⁵queries answeredcharacter comparisons, cumulative5 queriesScan each timeIndex, then queryone unit = one character comparison · 4 doubling roundsbreak-even at 5 queries Structures

The index that is the text

 0.010.11101001000QuicksortQuicksortQuicksortShellsortHeapsortMerge sortMerge sort with a cutoffInsertion sortBubble sortSelection sortn²time × space, as a multiple of n²n = 8,192 · light: auxiliary slots · dark: the input counted toonone under n² What a bound is

A floor under a product

 12481632640.1110line size B, array elementstransfers × cells, per n²heapsortShellsortquicksort, random pivotquicksort, first pivotthe read-only familyn = 8,192, memory 512 cells, LRUrandom input What a bound is

A product paid for in blocks

 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 What a bound is

The memory a product does not charge

 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 What a bound is

The lines a sort writes back

 fast memory, cells (log scale)transfers × fast memory, in n²/B (log scale)0.5124816321632641282565121,0242,0484,0968,192sorted buffer, with write-backsheap buffer, with write-backssorted buffer, reads alonebuffer of 64logarithmic scales What a bound is

A buffer that does not shift its tail

The library, page 5 of 5 — where time-space-frontier sits