Block swap algorithms

In computer algorithms, it simple to swap two elements of an array. It is also simple to swap two non-overlapping regions of an array of equal size. However, it is not simple to swap two non-overlapping regions of an array in-place that are next to each other, but are of unequal sizes. Three algorithms are known to accomplish this: Bentley's Juggling, Gries and Mills, and Reversal. All three algorithms are linear time O(N).

The reversal algorithm is the simplest to explain, using rotations. A rotation is an in-place reversal of array elements. This method swaps two elements of an array from outside in within a range. The rotation works for an even number of elements or an odd number of array elements. The reversal algorithm uses three in-place rotations to accomplish an in-place block swap: - Rotate region A - Rotate region B - Rotate region AB

The reversal algorithm parallelizes well, because rotations can be split into sub-regions, which can be rotated independently of others.