Where insertion sort actually wins — and it is not in the comparisons

Where insertion sort actually wins — and it is not in the comparisons

Mean over 60 random inputs at each size, both counts on one pair of axes. Insertion sort performs more comparisons than Merge sort at every size measured, including n = 4: the dashed pair never cross. The solid pair — total reads and writes — do cross, between n = 12 and n = 16. The familiar advice to fall back to insertion sort on small subarrays is right, and the reason is memory traffic rather than comparisons, which is a distinction the usual telling of it loses.

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