Powersort’s merge tree, built top-down: exactly peeksort’s recursion, except that “the middle” comes from a fixed, global grid — ½, then ¼ and ¾, … of the whole array — instead of from the current part. Morph between the two to see how little changes.
Top-down mergesort that peeks at the middle and cuts at the nearest run boundary instead. Step by step through the recursion: how i, j and the Δ’s are found in each call, and how the sign of a Δ says whether a run is known. The code is the one from the slides; the highlighted line is the one being executed. Merging is a single step here.
tiny.txt
can be pasted as it is. If every element is a number they are compared numerically, otherwise as strings.
Lines starting with # are comments.
@runs 5 3 3 14 1 2 asks for an input with exactly these run lengths
(the numbers 1 … n, every run increasing and every run boundary a descent), and @seed 3 picks another such input.
#runs=5,3,3,14,1,2 or #in=S,O,R,T,E,X,A,M,P,L,E; add &skip to skip the scans
and &present for the presentation view. &grid opens the tab with the global and the local grid
(plus &local to start from the local grid, &nogreen, &nopowers).