Comparisons against the number of natural runs, n = 8,192

Comparisons against the number of natural runs, n = 8,192

The input is built to contain exactly r natural runs, all of them spanning the whole value range, and nothing else about it changes. Timsort costs 8,191 comparisons at r = 1 and 49,518 at r = 181, and the dashed line is n + n log₂ r, which tracks the measurement to a spread of 1.57 — inside this site's 1.6 tolerance — up to the marked ceiling. Past r = 256 it stops: minrun extends every run shorter than 32, so an input with more runs than n/minrun is merged as though it had exactly that many, and its own run structure has stopped mattering. Merge sort has no such axis at all — the same count at every r, which is the difference between a sort that looks at its input and one that does not.

Drawn at 700 × 430, wide on the page. Everything above is what runs-and-cost 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 runs-and-cost. 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.