Last time, we looked at the rotation algorithm used by gcc libstdc++ for random-access iterators , and I concluded by noting that we’re going to make a shocking discovery.

As with all shocking discoveries, this one will shock disappoint you.

The discovery is that the gcc libstdc++ algorithm is the same as the forward-iterator algorithm !

Let’s run both algorithms on a problem where the two blocks are A1, A2, A3, B1, B2, B3, B4, B5. I’ll put the old forward iterator algorithm on top and the new gcc libstdc++ algorithm below.

first mid last

↓ ↓ ↓

A1 A2 A3 B1 B2 B3 B4 B5

↑ ↑ ↑

first mid last

We swap at first and mid , then advance both pointers. The two algorithms agree until first reaches the end of the original A block.

first mid last

↓ ↓ ↓

B1 B2 B3 A1 A2 A3 B4 B5

↑ ↑ ↑

first mid last

The old algorithm recurses in order to exchange A1, A2, A3 with B4, B4.…