Listsort Powersort

Powersort as implemented in CPython's listsort.c: every run stays exactly where it is in the input array A — nothing ever moves to a second full-size array. When two adjacent runs on the merge stack are combined, only the shorter of the two is copied into a scratch buffer of at most ⌈n/2⌉ elements; the merge then writes the combined result back into the gap the shorter run left behind (left-to-right if the left run was shorter, right-to-left if the right run was). Pushing a new run costs nothing — it already sits in A. This view shows exactly that data movement to and from the buffer; it does not depict CPython's galloping mode, which only changes how fast comparisons find the next element, not where data moves.

preset mode run lengths

speed

press play to run listsort Powersort.

each run — detected or merged — gets its own colour buffer empty (between merges) not yet scanned or a gap left behind after its run moved to the buffer 2 3 1 — run-boundary powers (shown once computed, removed once merged away)

CPython Powersort

procedure ListsortPowersort(A[0, n)):    run := next run in A▹ runs never move — they always stay in A    pending.push(run)    while more runs remain:        run := next run in A        p := power of the boundary between pending.top and run        while pending.size ≥ 2 and pending.second.power > p:            merge_at(pending.second, pending.top)▹ shorter side → scratch buffer; result fills the gap        pending.top.power := p        pending.push(run)▹ free — run already sits in A    while pending.size ≥ 2:▹ final cascade        if pending.size ≥ 3 and pending.third.len < pending.top.len:            merge_at(pending.third, pending.second)▹ keeps the final cascade balanced        else:            merge_at(pending.second, pending.top)▹ done: A[0, n) is sorted; the scratch buffer is free again

Companion animation for CPython's listsort.c merge strategy (see also the RPython/PyPy port); the run-detection and node-power merge policy itself is unchanged from Powersort — see the interactive explanation at power-sort.github.io. Here the focus is on the scratch buffer: only the shorter of two merging runs is ever copied out of A, and only for the duration of that one merge. Galloping (the exponential search CPython uses to skip ahead when one run is winning heavily) changes how fast elements are located, not where data moves, so it is not depicted here. The final cascade also shown here is CPython's own balancing rule: it merges the two second-from-top runs instead of the top two whenever that keeps the merge sizes more even.