= Solution
Treat the live <array> segment as a <FIFO queue> of runs. Remove its first two runs, append their merged result, and repeat:
``
PROCEDURE Sort(a, b: INTEGER; VAR c, d: INTEGER);
VAR x, y, z: INTEGER;
BEGIN
c := a; d := b;
WHILE c < d DO
x := Run(c, d);
IF x = d THEN RETURN END;
y := Run(x, d);
z := y-c;
Merge(c, x, y, d);
c := y;
d := d+z
END
END Sort;
``
Compute both run boundaries before writing the destination, which starts at the old `d`. The untouched suffix $u[y..d)$ is followed by the new merged run. The endpoints returned in `c,d` always describe the live <sequence>; obsolete values before `c` are ignored. As allowed, assume enough destination capacity.
For example, $[3,1,4,2]$ becomes the live <sequence> $[2,1,3,4]$, then $[1,2,3,4]$. The first merge combines $[3]$ and $[1,4]$, and the second combines $[2]$ and $[1,3,4]$.
$$
\boxed{u[c..d)\text{ contains the sorted input and }d-c=b-a.}
$$
Back to article page
