Sorting with less data movement than selection sort

Until recently, the wikipedia article on selection sort claimed it required less data movement than any other sorting algorithm. Luckily, that seems to have been just-about corrected; there's now an article (http://en.wikipedia.org/wiki/Cycle_sort) outlining a cycle sort algorithm that does "far fewer" array writes ("far fewer" is what Wikipedia says; it's about half as many, on average). I say, "just about corrected", because the cycle sort outlined there is still doing too many element moves (about as many as selection sort). The lines that go...

array[pos], item = item, array[pos]

still require three moves (because that's an exchange). If, however, you've got two item variables, item1 and item2, you can instead go...

array[pos], item2 = item1, array[pos]

half the time, and

array[pos], item1 = item2, array[pos]

the other half of the time, switching the sense of item1 and item2 each time (there's a very similar hack available in heapsort that reduces the number of index assignments). That change will reduce the average number of element moves by 1/3, to 2(n-f), where n is the number of elements in the array, and f is the number of elements already in their final position.

But that's still too many element moves. Applying a random permutation to n elements in place should require n+c-2*f element moves, where c is the number of cycles (including one-element cycles) - H(n) on average - and f is the number of elements already placed correctly (the number of one-element cycles), which yields: minimum 0, average n+H(n)-1, maximum 3n/2 moves. Even the "two item" version of cycle sort still requires on average almost twice as much data movement as it should.

I haven't been able to figure out an algorithm with a constant space overhead that achieves that. Maybe there isn't one. But I can see how to get closer to it, by maintaining more index variables. If you've got i index variables, the length of the current cycle can be reduced by i-1, at the cost of i element moves. The problem with that is handling duplicate values (it's bad enough in cycle sort but if you've got more index variables it gets much worse, because you have to skip over duplicates that will be moved into place when the cycle is "unraveled", but haven't actually been moved into place yet).

If the output isn't in the same location as the input, then n element moves will be sufficient (using a comparison counting sort, which will also be stable).