Radix sort — where it appears
Named by 5 essays across 3 fields — each of them below, with the objects they name alongside it.
The comparison that is not one comparison
Sorting 512 keys costs 3,955 comparisons whatever the keys are, and between 7,849 and 134,409 character examinations depending only on how much those keys have in common. The first number is the one every bound so far is stated in. The second is the one the machine pays, it grows without limit, and nothing here has ever counted it.
The sort that makes none of them
Every count on this collection is a count of comparisons, swaps, reads or writes, and radix sort makes zero of the first. On 65,536 keys it moves five times less data than merge sort, misses the cache three times more, and sits 954,037 comparisons under the floor no comparison sort can go beneath — which is not an achievement, because the floor was never a statement about it.
The digit a pass chooses for itself
A radix sort's digit width trades passes against the streams each pass scatters into, and the best width depends on the keys and the cache together: 8 bits for uniform keys through 32 KB, 11 through 256 KB, 16 for keys with few distinct values. A digit widened because the previous pass's counts were concentrated cannot find it, since in a least-significant-first sort one digit's counts say nothing about the next. One read that counts every byte at once, and a sample to size each field, can. Charged for both, the resulting plan is never worse than 1.23 times the best fixed width on any keys or cache measured. The best single fixed width reaches 1.50, and 11 bits reaches 3.61.
The question asked at every split
A range of rotations preceded throughout by one character writes the same run into the Burrows–Wheeler column in any order, and a sort that asked that once, of the ranges four characters leave, read 11% less than the transform. Asked at every split of a sort that partitions on one character at a time, it was predicted to read a fifth less on technical writing and an eighth less on the essays. It reads four fifths less — and nearly all of that is the change of sort, which the prediction expected to cost reading rather than save it. The question's own share, measured against the same sort without it, is 29% on technical writing and 14% on the essays.
A sort that infers the order
A radix quicksort that stops at every group of rotations preceded by one character reads about fourteen characters of a text for every symbol of its Burrows–Wheeler transform. Induced sorting, which reads the order of a third of the suffixes and derives the rest, was predicted to read three. It reads 6.1 on all sixteen streams, within 0.14 of each other, and the same at every length from a thousand characters to thirty-two thousand. The question the quicksort asks saves it nothing, as predicted, for a reason the prediction did not give: its last two passes read the transform's column itself, one character for every rotation, in order to sort.
Named alongside it
The objects these essays reach for when they reach for this one.
Measurement designBits per symbolBurrows-wheeler transformCacheCorpusCost modelCharacter comparisonComparison countComparison sortContext modelCounting conventionCounting sort