Last time, we noted that the std::rotate function requires only forward iterators. The algorithm we explored last time involved a clever sequence of reversals, but reversals require bidirectional iterators (one to iterator forward from the beginning and another to iterate backward from the end). How do you do it when you can only iterate forward?

Let’s set up the problem again. Suppose we want to swap these two blocks A and B.

We can early-out in the vacuous cases where either the A or B block is empty. For those cases, we can return without doing anything.

We start by swapping the elements at first and mid, then incrementing both pointers and repeating. Here’s what it looks after swapping a handful of items:

Let’s first take the case where the A block is bigger than the B block. In that case, the entire B block gets swapped to the start of the buffer, and a B-sized chunk of the first part of the A block (let’s call it A1) got swapped to the end of the buffer. There’s still a leftover chunk of the A block, call it A2, that hasn’t moved yet.

Okay, so the B block is in its final position, but the A1 and A2 blocks need to be swapped. Hey, I know how to swap two adjacent blocks: I call std::rotate on myself recursively! Since this is a tail recursive call, I can just move mid back to its original position at the start of the function and restart the algorithm.

The other case is where the A block is smaller than the B block.

In this case, we swap until we have used up all of the A elements. The entire A block gets swapped to the middle of the buffer, and an A-sized chunk of the start of the B block (call it B1) goes to the start of the buffer, with the leftover part of B (call it B2) stays at the end of the buffer.

Again, we can finish with a recursive rotate call, this time to swap A and B2.

In both cases, the recursive call is strictly smaller than the original call because we know that both A and B are nonempty: If either was empty, we would have performed a nop early-exit. Therefore, at least one element will be swapped before we reach the recursive call, and we consequently know that the recursion will eventually terminate.

The final case is where the A and B blocks are the same size. In that case, we have swapped all the B elements to the first half and all the A elements to the second half.

If we are lucky to get here, then we are done!

Note that we don’t need a special case handler for the equal-sized blocks case. We can treat as either the first or second case and let the early-out in the recursive call realize that there is nothing to do.

The number of swaps is n. You can calculate this recursively, since we perform k swaps to move the smaller block, and the recursive call (by induction) performs n − k swaps, for a total of n. You can also calculate this directly by observing that at each step, one element gets swapped into its final position (namely, at *first, just before we increment it).

Even though this algorithm and the bidirectional-iterator version both perform n swaps, the bidirectional-iterator version has better locality of reference, so it is preferred if available.

Next time, we’ll apply this to our original problem.

Bonus chatter: You don’t need to do a preliminary std::distance to figure out whether block A or block B is smaller. You can just start swapping elements, and make a note of which happens first: Does first reach the original mid (which means that the A block is smaller) or does mid reach last (which means that the B block is smaller). This “figure it out as you go” doesn’t change the complexity, but it does lower the constant a little bit because you don’t have to iterate through all of the larger block just to realize that it’s took big.