Sorting 512 strings as the shared prefix grows

Sorting 512 strings as the shared prefix grows

The same 512 keys in the same order, differing only in how many characters every one of them begins with. Merge sort makes 3,955 element comparisons at every point on this axis — the flat line — because the prefix changes no ordering. The characters it examines go from 7,849 to 134,409. A radix sort, which compares nothing, reads 18,317 characters and does not care.

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

1 essay calls two-units. 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.