Swapping two blocks of memory inside a larger block, in constant memory

Summary

Suppose you have a large block of memory, and you want to swap two blocks that reside inside that large block. For concreteness, say you have a block of memory of the form A1, A2, B1, B2, C1, C2, D1, D2, D3, E1, and you want to swap the B’s and D’s, producing A1, A2, D1, D2, D3, C1, C2, B1, B2, E1. A1 A2 B1 B2 C1 C2 D1 D2 D3 E1 ⤩ A1 A2 D1 D2 D3 C1 C2 B1 B2 E1 Like, say, you have a double-null-terminated string and you want to swap two strings in it. Now, of course, the easy way would be just to allocate a second buffer equal in size to the original buffer and copy the strings to the second buffer in the desired order. But just as an exercise, can you do this without allocating additional memory? Here’s a hint: There is an algorithm to swap two adjacent buffers using no additional space. In C++, this algorithm is implemented by the std::rotate method. For example, if you have a block of memory of the form X1, X2, Y1, Y2, Y3, then you can call std::rotate(v.begin(), v.begin() + 2, v.end()) to get Y1, Y2, Y3, X1, X2. X1 X2 Y1 Y2 Y3 ⤩ Y1 Y2 Y3 X1 X2 The function is called rotate because you can view it as taking the combined buffer and doing a circular rotation until Y1 is the new first element. You can perform the desired exchange of non-adjacent blocks by performing three rotations. Starting with A1, A2, B1, B2, C1, C2, D1, D2, D3, E1, your first rotation exchanges the B’s with the C’s: your second rotation exchanges the B’s with the D’s, and your final rotation exchanges the C’s with the D’s. A1 A2 B1 B2 C1 C2 D1 D2 D3 E1 ⤩ A1 A2 C1 C2 B1 B2 D1 D2 D3 E1 ⤩ A1 A2 C1 C2 D1 D2 D3 B1 B2 E1 ⤩ A1 A2 D1 D2 D3 C1 C2 B1 B2 E1 (There are other ways to accomplish this with three rotations.) But you can do better. The way rotation works is by reversing the two buffers separately, and then reversing the combined buffer. Starting with X1, X2, Y1, Y2, Y3, we reverse the X’s (producing X2, X1) and reverse the Y’s (producing Y3, Y2, Y1), and then reverse the whole thing, giving a fina...