 Array rotation

A right array rotation by $k$ sends the entry originally at offset $j$ to offset $(j+k)\mathrm{mod}n$ for nonempty length $n$. Equivalently it changes adjacent blocks $AB$ into $BA$ when $|B|=k$. Identity rotations include $k=0$ and $k=n$.

Three reversals implement the operation: $AB\to A^{R}B\to A^R{B}^R\to BA$. Alternatively repeatedly use a block swap to put the smaller block in its final position and recurse on the remaining unresolved segment. Replacing that tail recursion by parameter updates gives constant auxiliary storage. If $S(a,b)$ counts swaps for blocks of lengths $a,b>0$, then $S(a,a)=a$ and $S(a,b)=\min (a,b)+S(\min (a,b),|a-b|)$ for unequal lengths. The Euclidean algorithm shows by induction that $S(a,b)=a+b-\gcd (a,b)$, so a right rotation uses $n-\gcd (n,k)$ element swaps for $0<k<n$.