600 runs of quicksort, random pivot at n = 512

600 runs of quicksort, random pivot at n = 512

Every bar is the number of independent random inputs that cost that many comparisons. The mean is 4945; the median is 4908; the worst of 600 runs cost 6,543, which is 1.32 times the mean. The distribution is tight — a relative standard deviation of 6.8% — and skewed to the right, which is the shape that makes "on average" a defensible thing to say about this algorithm and a misleading thing to say about the version that takes the first element as its pivot.

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

6 essays call quicksort-spread. 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.