A measured sort against the floor under every sort

A measured sort against the floor under every sort

The lower line is (n/B)·log_{M/B}(n/B), which is a lower bound on the transfers any algorithm needs to sort n elements in this model — not a bound on merge sorts, on all of them. The upper line is a real external merge sort, counted. The ratio runs from 2.29 to 3.20: the algorithm is within a constant of optimal, and the constant is the part the notation drops.

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

2 essays call sort-floor-gap. 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.