Powersort where runs are lists of pages of size P ≈ √(n / lg n):
besides the ⌈n/P⌉ pages of the input array A, we borrow only
lg n + O(1) extra pages (B). Detected runs are copied page by page into
pages from a free-page pool; fully scanned pages of A join the pool and are reused for the
output of future merges. Merges proceed page by page — every drained input page immediately returns
to the pool. Pages of a run stay permuted in memory until the very end; a final pass puts the
pages of the sorted result back into A in order. The top panel shows physical memory,
the bottom panel shows each live run as its logical, in-order sequence of pages
(the little label under each page tells you where it physically lives — hover a page to highlight
its twin in the other panel).
press play to run virtual-memory Powersort.
each run — detected or merged — gets its own colorfree / stale pagenot yet scanned (ghost ramp = original data)p = 2 — run-boundary power (on the logical run whose right edge it marks)
Virtual-Memory Powersort
procedure VirtualMemoryPowersort(A[0, n)): P := ≈√(n / lg n); view A as ⌈n/P⌉ pages▹ a run = a list of pages pool := the lg n + O(1) extra pages B▹ LIFO pool of free pages curr := extract next run▹ copy it page-wise into pool pages; scanned A-pages join the poolwhile curr is not the last run: next := extract next run p := power of the boundary between curr and nextwhile stack.top.power > p: curr := merge(stack.pop() ⋈ curr)▹ page by page into pool pages; drained pages return to the pool stack.push(curr with power p)▹ records the page list only — no data moves curr := nextwhile stack is not empty:▹ final cascade curr := merge(stack.pop() ⋈ curr)for each page slot s of A, left to right:▹ put the pages back in orderif slot s still holds a live page: move it to a pool page copy page s of curr into slot s▹ its old page returns to the pool▹ done: A[0, n) is sorted; only the extra pages remain in the pool
