Record size — where it appears
Named by 5 essays across 3 fields — each of them below, with the objects they name alongside it.
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.
The exchange rate nobody wrote down
Three earlier essays have said in passing that the ranking would change if the elements were large records. None of them computed it. Computed, selection sort goes from second-worst of seven at four bytes a record to best of seven at five hundred and twelve — and the crossover against each rival is a division that takes one line.
The order equal keys keep
Four of the eight sorts here leave every pair of equal keys in the order it arrived in and four move between 1,209 and 2,403 pairs, and none of the four counts every plate here reports can tell them apart. Decorating each record with its arrival position makes any of them stable, for four thousand words and between 0.05 and 1.64 times its comparisons — a charge of 64% on Shellsort and a saving of 95% on quicksort, because the ties stability has to break are the ties a two-way partition chokes on.
A lookup that stops caring how wide an entry is
Buckets of eight entries aligned to a cache line read 1.20 lines a lookup when an entry is eight bytes and 19.25 when it is 128, because the bound was arithmetic about alignment and the arithmetic stops holding. Keeping one byte of each key's hash in a separate array and the entries in a parallel one reads 2.21 lines at every width from four bytes to sixty-four — and for a key the table does not hold, 2.05 against 31.98.
The request no price of memory would make
libstdc++'s stable_sort asks for a buffer of half the input. Priced in element moves against the memory held, every buffer from nothing to a buffer as large as the input has a range of memory prices at which it is the cheapest — except that one. A quarter of the input costs 1.4% more moves; a full buffer, merging out of place, saves 8% more for twice the memory; and the half-sized request sits above the line between them at every size measured. The record size, predicted to move the answer, does not: moves and memory both cost in proportion to it.
Named alongside it
The objects these essays reach for when they reach for this one.
Comparison countSpace time tradeData movementMerge sortSpecificationStabilityDesign parameterLibrary sortAlignmentBinary searchCacheCache line