Pingpong Powersort

Powersort with pingpong merging: runs on the merge stack live in the buffer B, while the current run lives in the input array A. Merges combine the top run of the stack (in B) with the current run (in A) and write the output to A if more merges follow, or to B (right-to-left) if the merged run is pushed. Runs that are pushed without merging are copied to B. The final merges write to A, so the sorted result always ends up in the input array — with no separate clean-up copying.

preset mode run lengths

speed

press play to run pingpong Powersort.

detected runs merged run (output of a merge) free / stale (contents irrelevant) not yet scanned 2 3 1 — run-boundary powers (shown once computed, removed once merged away)

Pingpong Powersort

procedure PingpongPowersort(A[0, n)):    curr := next run in A▹ runs are always detected in A    while curr is not the last run:        next := next run in A        p := power of the boundary between curr and next        while stack.secondTop.power > p:▹ ≥ 2 merges pending            curr := merge(stack.pop() ⋈ curr) into A▹ stack run is in B, curr in A        if stack.top.power > p:▹ exactly 1 merge pending            curr := merge(stack.pop() ⋈ curr) into B▹ right-to-left (in‑place in B)        else:            copy curr from A to B▹ push without merging        stack.push(curr with power p)▹ curr now lives in B        curr := next    while stack is not empty:▹ final cascade        curr := merge(stack.pop() ⋈ curr) into A▹ result ends up in A▹ done: A[0, n) is sorted, B is free again

Companion animation for the pingpong merging strategy; 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 where each run lives (input array A vs. buffer B) over time.
For further details, see Virtual-Memory Powersort.