[MS] Rotation revisited: Shuffling more than three blocks, and other small notes - devamazonaws.blogspot.com
A few small notes on rotation before you get sick of it. (Too late!) Reducing the number of rotations in the discontiguous swap problem from three to two also shows how the solution can be generalized to shuffling an arbitrary number of variable-sized blocks: Given k blocks, of total size n , you can shuffle them arbitrarily in at most kn swaps in constant space: Take the block that goes first and rotate it to the front, which takes n swaps. Then recurse on what's left. You can reduce the number of swaps by comparing the sizes of the block that goes first and the block that goes last and choose to swap the larger block to the corresponding extreme. I guess you could use this for sorting, but it's probably enough of a hassle that you'll just take the penalty of allocating a second block of memory rather than trying to be clever and doing it in-place. In online discussion of this article, I saw a number of people say, "You can do this with the XOR trick," b...
