Block swap algorithms
In computer algorithms, block swap algorithms swap two regions of elements of an array. It is simple to swap two non-overlapping regions of an array of equal size. However, it is not as simple to swap two contiguous regions of an array of unequal sizes. A few well-known algorithms can accomplish this: Bentley's juggling, Gries-Mills rotation, triple reversal algorithm, conjoined triple reversal algorithm and Successive rotation.
Triple reversal algorithm
The triple 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 or 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
Gries-Mills and reversal algorithms perform better than Bentley's juggling, because of their cache-friendly memory access pattern behavior.
The triple reversal algorithm parallelizes well, because rotations can be split into sub-regions, which can be rotated independently of others.