### Gries and Mills Block Swapping

Bentley also describes a block-swapping algorithm by Gries and Mills in his book and the article. The algorithm swaps the largest equal-sized non-overlapping blocks available at each step. The main idea is to use swap as an operation as follows from his article:

*A*is the left subarray,*B*is the right subarray — that is, the starting point is*AB*- If
*A*is shorter, divide*B*into*B*and_{L}*B*, such that length of_{R}*B*equals the length of_{R}*A* - Swap
*A*and*B*to change_{R}*AB*into_{L}B_{R}*B*_{R}B_{L}A - Recur on the two pieces of
*B* - Once
*A*and*B*are of equal lengths, swap*A*and*B*

Figure 6 shows the steps:

**Figure 6.**

Red indicates the shorter of the two subarrays. The red subarray is *A*, and the blue subarray is *B*. The length of *A* is two, which is shorter than the length of *B*, which is five, and *B* is divided into *B _{L}* and

*B*, where

_{R}*B*is of equal length to

_{R}*A*. At this point

*B*contains elements 5 and 6.

_{R}*A*and

*B*are swapped, which is shown in the second row.

_{R}In the third row, the original *A* subarray (elements 0 and 1) is at its final location, shown in grey. The smaller of the *B _{L}* and

*B*is colored red, and the next level of recursion proceeds with these two subarrays. Elements 5 and 6 become the red subarray

_{R}*A*, and the blue subarray of elements 2, 3 and 4 becomes

*B*. Since

*A*is shorter than

*B*, the subarray

*B*is split into

*B*and

_{L}*B*consisting of elements (2) and (3 and 4), respectively. In row four, subarrays

_{R}*A*and

*B*are swapped. The algorithm continues to recurse, until the remaining subarrays are of the same size, at which point they are swapped. The Gries-Mills Swap non-recursive implementation is shown in Listing Two.

_{L}#### Listing Two: The Gries-Mills non-recursive implementation.

template< class _Type > inline void swap( _Type* x, int a, int b, int m ) { while( m-- > 0 ) exchange( x[ a++ ], x[ b++ ] ); } template< class _Type > inline void block_swap_Gries_and_Mills( _Type* a, int l, int m, int r ) { int rotdist = m - l + 1; int n = r - l + 1; if ( rotdist == 0 || rotdist == n ) return; int p, i = p = rotdist; int j = n - p; while ( i != j ) { if ( i > j ) { swap( a, p-i, p, j ); i -= j; } else { swap( a, p-i, p+j-i, i ); j -= i; } } swap( a, p-i, p, i ); }

### Reversal Algorithm

The third algorithm Bentley describes is the Reversal, which is the simplest. The Reversal algorithm uses rotation as the operation instead of swap. Figure 7 shows the steps:

**Figure 7.**

The first row is the original array, where the red and the blue subarrays are to be exchanged. In the second row, the elements of the red array are rotated. Rotation is an operation that can be done in-place for any number of elements (odd or even), reversing the order of elements within an array. In the third row, the elements of the blue subarray are rotated. Going from the third row to the last row, the entire array is rotated, resulting in the red and blue subarrays being exchanged. The implementation is shown in Listing Three.

#### Listing Three: Reversal Algorithm.

// reverse/mirror a range from l to r, inclusively, in-place template< class _Type > inline void reversal( _Type* a, int l, int r ) { while( l < r ) exchange( a[ l++ ], a[ r-- ] ); } // Swaps two sequential subarrays ranges a[ l .. m ] and a[ m + 1 .. r ] template< class _Type > inline void block_exchange_reversal( _Type* a, int l, int m, int r ) { reversal( a, l, m ); reversal( a, m + 1, r ); reversal( a, l, r ); }

The inverse variation on this method rotates the whole array, followed by the rotations of the two subarrays, as shown in Figure 8:

**Figure 8.**

Going from the first row to the second, the entire array is rotated. At this point, the blue and red subarrays are in their proper places, but each are in reverse order. In the third row, the blue subarray is rotated. In the last row, the red subarray is rotated. The result is a red and blue block exchange. Listing Four shows an implementation of this method.

#### Listing Four: Reversal Algorithm in Reverse.

template< class _Type > inline void block_exchange_reversal_reverse_order( _Type* a, int l, int m, int r ) { reversal( a, l, r ); int m_in_destination = r - ( m - l + 1 ); reversal( a, l, m_in_destination ); reversal( a, m_in_destination + 1, r ); }