Where each algorithm looks, and when

Where each algorithm looks, and when

Every array access from one run of each algorithm on 256 random elements: time along the horizontal axis, array index up the vertical. Merge sort makes 49% of its accesses to the next element or the same one; Heapsort makes 15%. That difference is invisible in the comparison count and is most of what the machine feels.

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

8 essays call access-pattern. 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.