Block swap algorithms

This article provides insufficient context for those unfamiliar with the subject. Please help improve the article by providing more context for the reader. (July 2019) (Learn how and when to remove this message)

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 simple to swap two non-overlapping regions of an array in-place that are next to each other, but are of unequal sizes (such swapping is equivalent to array rotation). Three algorithms are known to accomplish this: Bentley's juggling (also known as dolphin algorithm ^[1]), Gries-Mills, and reversal algorithm.^[2] All three algorithms are linear time O(n), (see Time complexity).

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 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 reversal algorithm parallelizes well, because rotations can be split into sub-regions, which can be rotated independently of others.