Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming / 4 / c / ii

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.If $a<b$, split $B=B_1{B}_2$ with $|B_2|=a$. The first block swap sends $A{B}_1{B}_2$ to $B_2{B}_{1}A$; $A$ is now in its final suffix. Rotate the remaining prefix of length $b$ right by $b-a$ to send $B_2{B}_1$ to $B_1{B}_2$. If $a>b$, split $A=A_1{A}_2$ with $|A_1|=b$. The swap sends $A_1{A}_{2}B$ to $B{A}_2{A}_1$; the fixed prefix is $B$, and rotating the remaining length-$a$ suffix right by $b$ restores $A_1{A}_2$. In both cases the exchanged segments are disjoint.

The remaining length strictly decreases, so induction on $n$ proves algorithm termination and correctness. 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.