= Solution
Replace the sole recursive call by updates to the current segment's parameters:
``
PROCEDURE rotate(i, n, k: INTEGER);
VAR a, b: INTEGER;
BEGIN
WHILE (k > 0) AND (k < n) DO
a := n-k; b := k;
IF a = b THEN
blockswap(i, i+a, a);
RETURN
ELSIF a < b THEN
blockswap(i, i+b, a);
n := b; k := b-a
ELSE
blockswap(i, i+a, b);
i := i+b; n := a; k := b
END
END
END rotate;
``
The <loop invariant> is that every position outside the current unresolved segment already has its final value, while rotating the current segment by the current `k` completes the original <array rotation>. The block decompositions in part (ii) prove preservation. The positive unresolved length decreases in each continuing branch; the equal-block branch finishes immediately. \b[The same rotation now uses $O(1)$ auxiliary space], including control storage, and leaves the rest of the <array> untouched.
Back to article page
