External merge sort, measured in block transfers

External merge sort, measured in block transfers

Every point is a real sort of n random values through a modelled memory, with the transfers counted as they happen rather than computed from a formula. The steps are the passes: each time the number of initial runs crosses a power of the fan-in, the whole file is read and written once more. At M = 256 the fan-in is 7 and the sort takes 4 passes at the largest size here; at M = 1024 it takes 3. More memory does not make the passes cheaper, it makes them fewer.

Drawn at 700 × 420, wide on the page. Everything above is what sort-passes 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 sort-passes. 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.