= Solution
Let $a=n-k$ and $b=k$ be the lengths of the left and right blocks. Exchange the smaller block with the equally long block at the opposite end.
``
PROCEDURE rotate(i, n, k: INTEGER);
VAR a, b: INTEGER;
BEGIN
IF (k = 0) OR (k = n) THEN RETURN END;
a := n-k; b := k;
IF a = b THEN
blockswap(i, i+a, a)
ELSIF a < b THEN
blockswap(i, i+b, a);
rotate(i, b, b-a)
ELSE
blockswap(i, i+a, b);
rotate(i+b, a, b)
END
END rotate;
``
If $a<b$, split $B=B_1B_2$ with $|B_2|=a$. The first <block swap> sends $AB_1B_2$ to $B_2B_1A$; $A$ is now in its final suffix. Rotate the remaining prefix of length $b$ right by $b-a$ to send $B_2B_1$ to $B_1B_2$. If $a>b$, split $A=A_1A_2$ with $|A_1|=b$. The swap sends $A_1A_2B$ to $BA_2A_1$; the fixed prefix is $B$, and rotating the remaining length-$a$ suffix right by $b$ restores $A_1A_2$. In both cases the exchanged segments are disjoint.
The remaining length strictly decreases, so <induction> on $n$ proves <algorithm termination> and correctness. \b[This implements the block-exchange rotation.] It uses only simple explicit variables, but its recursive call stack can have $\Theta(n)$ depth when one block has length $1$; the iterative version removes that extra storage.
Back to article page
