Exact sort - sorting with few move operations

A while ago, I found a somewhat interesting sorting algorithm named Exact-Sort, which is introduced with the following somewhat bold claim:


No sort algorithm can sort an array with less position changing (relocating) than Exact-Sort.

While the claim is perhaps not as impressive as the fact that the website is still hosted on Geocities, it still caught my interest and I decided to have a look at it. Note that even though it performs few moves, it performs an unreasonable number of comparisons and uses additional memory, so it's only suitable to sort objects that are really expensive to move and cheap to compare.

How does it work?

Here is how the algorithm works: it picks the first element and counts the number of elements smaller than this one to compute its final position once everything is sorted (plus some additional trickery to handle duplicate elements). Then it puts the element at that position in a temporary variable and moves the first element in its final position. Then it starts again with the element that was at the final position of the first elements. It does so until the final position of one element corresponds to the first position. Then, it looks for another unsorted element and performs another such cycle. Then it continues to do so until the collection is sorted.

Yes, but...

Unfortunately, the algorithm doesn't (really) hold its promise: in this form, it does roughly a number of moves equivalent to that of a selection sort. The problem is that it swaps the elements once it has found its position, which means that it always has to move an element to a temporary location before moving it back into the collection. In other words, while it indeed relocates an object only once, it still has to swap it with a temporary location, which means that it performs two additional moves. Ideally, we should have to store only one element per cycle in a temporary location and move all the other ones directly from their original position to their final posi

I have to agree with sehe, this is well written. Just a couple of recommendations for maintainability.

Prefer standard algorithms

The immediate things that come to mind is the opportunity to use standard algorithms in your functions. real_index() could be written using std::find().

e: Unfortunately, this solution only works if you had a bit_vector container (not std::vector) that specialized the various ` functions like a std::find()` that processed 64 bits at a time rather than 1 bit at a time.

Always initialize variables

RandomAccessIterator dest; // Final destination of the current element
if (positions.empty()) 
{
  dest = get_destination(first, last, compare, sorted,
                         *start, start);
}
else 
{
  dest = get_destination(first, last, compare, sorted,
                         *positions.top(), start);
}

This rule is pretty strict as it improves maintainability and protects against the used-before-set class of errors.

const auto& elem = positions.empty() ? *start : *positions.top();
RandomAccessIterator dest = get_destination(first, last, compare, sorted,
                                            elem, start);

StackExchange Code Review Q#111962, answer score: 5