{"id":112376,"date":"2026-06-02T07:00:00","date_gmt":"2026-06-02T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=112376"},"modified":"2026-06-02T20:22:28","modified_gmt":"2026-06-03T03:22:28","slug":"20260602-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20260602-00\/?p=112376","title":{"rendered":"Rotation revisited: Another unidirectional algorithm"},"content":{"rendered":"

Some time ago, we looked at the problem of swapping two blocks of memory that reside inside a larger block, in constant memory<\/a>, and along the way, we learned about std::rotate<\/code> which swaps two adjacent<\/i> blocks of memory (not necessarily the same size).<\/p>\n

I noted in a postscript that clang’s libcxx<\/a> and gcc’s libstdc++<\/a> contain specializations of std::rotate<\/code> for random-access iterators that view the operation as a permutation and decomposes the permutation into cycles.<\/p>\n

I was mistaken.<\/p>\n

The implementation in gcc’s libstdc++ has special cases for single-element rotations, but in the general case, it uses a different algorithm.<\/p>\n

Let’s call the blocks of memory to be exchanged A and B, where A is made up of elements A1, A2, A3, and so on; and block B has elements B1, B2, B3, and so on. Without loss of generality, suppose the A block is smaller. (If not, we can just mirror the algorithm.) And for concreteness let’s say that the elements are A1, A2, A3, B1, B2, B3, B4, B5.<\/p>\n\n\n\n\n\n
A1<\/td>\nA2<\/td>\nA3<\/td>\nB1<\/td>\nB2<\/td>\nB3<\/td>\nB4<\/td>\nB5<\/td>\n<\/tr>\n
\u2191<\/td>\n <\/td>\n <\/td>\n\u2191<\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n\u2191<\/td>\n<\/tr>\n
first<\/td>\n <\/td>\n <\/td>\nmid<\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\nlast<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Exchange elements at first<\/code> and mid<\/code>, then move both iterators forward. After the first step, we have this:<\/p>\n\n\n\n\n\n
B1<\/td>\nA2<\/td>\nA3<\/td>\nA1<\/td>\nB2<\/td>\nB3<\/td>\nB4<\/td>\nB5<\/td>\n<\/tr>\n
 <\/td>\n\u2191<\/td>\n <\/td>\n <\/td>\n\u2191<\/td>\n <\/td>\n <\/td>\n <\/td>\n\u2191<\/td>\n<\/tr>\n
 <\/td>\nfirst<\/td>\n <\/td>\n <\/td>\nmid<\/td>\n <\/td>\n <\/td>\n <\/td>\nlast<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

After three steps, we have moved all of the A’s out and replaced them with an equal number of B’s.<\/p>\n\n\n\n\n\n
B1<\/td>\nB2<\/td>\nB3<\/td>\nA1<\/td>\nA2<\/td>\nA3<\/td>\nB4<\/td>\nB5<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n <\/td>\n\u2191<\/td>\n <\/td>\n <\/td>\n\u2191<\/td>\n <\/td>\n\u2191<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n <\/td>\nfirst<\/td>\n <\/td>\n <\/td>\nmid<\/td>\n <\/td>\nlast<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

But don’t stop. Keep on going until mid<\/code> reaches last<\/code>.<\/p>\n\n\n\n\n\n
B1<\/td>\nB2<\/td>\nB3<\/td>\nB4<\/td>\nB5<\/td>\nA3<\/td>\nA1<\/td>\nA2<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n\u2191<\/td>\n <\/td>\n <\/td>\n\u2191<\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\nfirst<\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\nmid
\nlast<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

All of the B’s have been swapped to their final positions, but the A’s are jumbled.<\/p>\n

But you can predict the exact nature of the jumbling. The A block is in two chunks. If we let n<\/var> be the total number of elements |A| + |B| and a<\/var> be the number of elements in A, then the first chunk has the final n<\/var> % a<\/var> elements, and the second chunk has the initial a<\/var> \u2212 (n<\/var> % a<\/var>) elements.<\/p>\n

Therefore, we can recursively rotate the two pieces of the A block to finish the job. Move mid<\/code> to first<\/code> + (n<\/var> % a<\/var>) and restart the algorithm.<\/p>\n

This algorithm performs n<\/var> \u2212 1 swaps. You can calculate this inductively by observing that we perform |B| swaps, and then recursively rotate |A|. Or you can calculate this directly by observing that each swap moves one element to its final position, except that the final swap moves two elements to their final position.<\/p>\n

The locality of this algorithm fairly good. The first<\/code> iterator moves steadily forward, and the mid<\/code> iterator moves forward most of the time, with at most O<\/var>(log (min(|A|, |B|)) backward resets.<\/p>\n

Next time, we’ll make a shocking discovery about this algorithm.<\/p>\n","protected":false},"excerpt":{"rendered":"

Moving in a straight line, in a different way.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-112376","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"

Moving in a straight line, in a different way.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/112376","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=112376"}],"version-history":[{"count":1,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/112376\/revisions"}],"predecessor-version":[{"id":112377,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/112376\/revisions\/112377"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=112376"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=112376"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=112376"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}