What randomising the pivot buys, n = 512

What randomising the pivot buys, n = 512

For each pivot rule: the range of comparison counts over 400 random inputs (the bar), and the count on an already sorted array (the marker). Taking the first element as pivot costs 130,816 comparisons on sorted input — 26 times its random-input mean, and the quadratic behaviour the algorithm is supposed to avoid. Choosing the pivot at random costs 5,490 on the same input. Randomisation does not make the bad case impossible; it makes it independent of the input, so an adversary who knows the data cannot choose it.

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

4 essays call pivot-rules. 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.