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

The thread: In place is a claim

Three sorts described with the same two words hold one slot, twenty-two slots and four thousand slots at their peak. The phrase has no number in it, and once there is one, the algorithm most often called in-place turns out not to be.
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 other axis

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.

 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

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.

 —execution—intention87777776569888888765one unit = one subproblem given a value100 cells computed, 20 held at once The other axis

The table nobody has to keep

A million-cell table, computed cell for cell in the same order, holding two thousand cells at its peak instead of a million. The saving is exactly (n+1)/2, it costs nothing on any operation counter, and what it buys is paid for with the one thing the table was for.

 050100150elements of buffer obtained — the request, then each halving the allocator falls back toper key sorted32,7688,1922,0485121283282nonemovescomparisonsn = 65,536, distinct keys, random ordera swap counts as three moves What the libraries do

A guarantee that depends on an allocation

The C++ standard promises std::stable_sort N log₂ N comparisons if enough extra memory is available, and N (log₂ N)² otherwise. On 65,536 keys the library's own structure, denied its buffer entirely, makes 1,366,510 comparisons — a third more than with it, and twelve times under what the standard allows. What it spends instead is moves: 10.4 million against 1.2 million, 94% of them rotations. The standard bounds the count that barely changes and says nothing about the one that grows as n log² n.

 ε = 0.0515 → 29 (1.93×)ε = 0.0238 → 73 (1.92×)ε = 0.0177 → 136 (1.77×)ε = 0.005152 → 270 (1.78×)ε = 0.002397 → 674 (1.70×)reportedoccupied at the peak20,000 arrivals · lognormalpeak = resident + period, to 14% The other axis

The tuples a summary does not report

A Greenwald–Khanna summary at ε = 0.01 answers `tuples` with seventy-seven. Watched through the run it holds a hundred and thirty-six. The gap is the compression period, it is 1.70 to 1.93 times across every tolerance measured, and it is the number a deployment has to allocate.

 1/41/81/161/641/2561/10240.10.3131030buffer, share of the inputmoves a keythe libraryruns read, no trimruns read, trimmedsixteen batches, 5% overlap, 65,536 keysschedule smallest-first What the libraries do

The skip the split already made

A stable merge with too small a buffer is split by rotation, and the rotation was proposed to be the waste: gallop from each end of a merge first, set aside what is already in place, and rotate only the rest. On a sorted file with late arrivals the gallop sets aside two thirds of the keys in its split merges and saves half a per cent of the moves, because the library's split — halve one run, binary-search the other — had already found those stretches by bisection and moved nothing there. Where the gallop pays is the merge that fits the buffer, which copies its whole shorter run out and back: on sixteen overlapping batches it takes the sort from 1.92 moves a key to 0.13, and makes a larger buffer stop costing more.

 125102050buffer, as a share of the inputwrites ÷ the floor1/41/161/641/2561/1024sixteen batches, 5% overlapa random tenth appendeda late tenth appendedfour runssixteen runsrandom keys65,536 keys, trimmed sortone: the floor itself What the libraries do

The moves no stable sort can skip

Any sort must move every key that starts out of place, and with one spare cell it must spend one more move on each cycle of the permutation. Against that floor, a stable merge sort trimmed to the keys not already in place moves 1.46 times the least possible on records written in overlapping batches — the two thirds the prediction named, and for its reason. On a sorted file with a late tenth appended it was predicted within twice the floor and moves 15 times it, because the late tenth arrives in random order and sorting it among itself is two thirds of the work.

All threads