Exact sort - sorting with few move operations

Question

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 position.

To solve this problem, I have devised a variant of the algorithm that stacks the positions of the elements to move and actually moves them only once the end of a cycle has been reached. It takes more memory to store the positions, but it should always perform between \$0\$ and \$\frac{2}{3}(n - 1)\$ move operations to sort the collection (where \$n\$ is the size of the collection). In comparison, a typical selection sort performs \$3n\$ move operations.

Implementation

Enough talk, here is my C++14 implementation of this variant of the algorithm:

#include <cstddef>
#include <iterator>
#include <stack>
#include <utility>
#include <vector>

// Returns the index of the position of the nth element of the
// collection not already in its place
template<typename RandomAccessIterator>
auto real_index(RandomAccessIterator first, RandomAccessIterator last,
                const std::vector<bool>& sorted, std::size_t n)
    -> RandomAccessIterator
{
    // Number of encountered elements not already sorted
    std::size_t unsorted = 0;

    for (std::size_t i = 0 ; i < sorted.size() ; ++i)
    {
        if (not sorted[i])
        {
            ++unsorted;
        }

        if (unsorted == n + 1)
        {
            return first + i;
        }
    }
    return last;
}

// Returns the index of the first element in the collection
// that hasn't been sorted yet
template<typename RandomAccessIterator>
auto first_false(RandomAccessIterator first, RandomAccessIterator last,
                 const std::vector<bool>& sorted)
    -> RandomAccessIterator
{
    return real_index(first, last, sorted, 0);
}

// Returns the destination of the given value, where the destination
// corresponds to the final position of the given value once the whole
// collection has been sorted
template<typename RandomAccessIterator, typename T, typename Compare>
auto get_destination(RandomAccessIterator first, RandomAccessIterator last,
                     Compare compare, const std::vector<bool>& sorted,
                     const T& value, RandomAccessIterator start)
    -> RandomAccessIterator
{
    // Number of unsorted elements smaller elements than value
    std::size_t count = 0;

    for (auto it = first ; it != last ; ++it)
    {
        if (not sorted[it - first] && compare(*it, value) && it != start)
        {
            ++count;
        }
    }
    return real_index(first, last, sorted, count);
}

template<typename RandomAccessIterator, typename Compare>
auto exact_sort(RandomAccessIterator first, RandomAccessIterator last,
                Compare compare)
    -> void
{
    if (first == last) return;

    // Which elements are already sorted, and which ones still
    // need to be sorted
    std::vector<bool> sorted(std::distance(first, last), false);

    // Element where the current cycle starts
    RandomAccessIterator start = first;

    // Stack of elements, top is the current element
    std::stack<
        RandomAccessIterator,
        std::vector<RandomAccessIterator>
    > positions;

    while (true)
    {
        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);
        }

        // There is nothing else to sort
        if (dest == last) return;

        // Mark the destination as "sorted"
        sorted[dest - first] = true;

        // When the beginning of the current cycle is the same as the
        // destination of the element to sort, we have reached the end
        // of the cycle
        if (dest == start)
        {
            // If the stack is empty, it means that the starting point
            // is already in its final position, do nothing

            if (not positions.empty())
            {
                // Move elements to their final positions
                auto tmp = std::move(*dest);
                while (not positions.empty())
                {
                    *dest = std::move(*positions.top());
                    dest = positions.top();
                    positions.pop();
                }
                *dest = std::move(tmp);
            }

            // The next cycle starts at the first unsorted element
            // of the collection
            start = first_false(first, last, sorted);

            // If there is no such element, it means that the collection
            // is already sorted
            if (start == last) return;
        }
        else
        {
            // Push the destination on the top of the stack
            positions.push(dest);
        }
    }
}

My original implementation also handles projections but it's a bit difficult to explain and trivial to add (and almost impossible to get wrong), so I skipped it for the review. All of these functions live in a detail namespace and are only given values from other functions (the users never use them directly), otherwise I would also have provided a version that doesn't take a comparator.

Conclusion

To sum up, this algorithm should always perform an optimal number of move operations (the ideal algorithm to sort fridges by price says the original description on Geocities), but always performs \$O(n²)\$ comparisons and uses \$O(n)\$ auxiliary memory.

Is there any way I could improve this algorithm (performance, efficiency, correctness, etc...) without losing its move-optimal property?

---

Trivia: Apparently, the original Exact-Sort corresponds to another sorting algorithm known as cycle sort, except that Exact-Sort stores a boolean array to perform an optimized lookup. Otherwise, the cycles logic and the aim of both algorithms (minimal number of writes to the original array) are pretty much the same. I realize that my algorithm has a slightly different goal, so it might be a good idea to find another name for it.

Answer 1

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<bool>) that specialized the various <algorithm> 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);

Answer 2

I had some time to work on the algorithm a bit since I asked the question and tweaked it a bit. Here is what changed:

A small optimization

real_index does a bit too much work: it always check whether unsorted == n + 1, even when unsigned hasn't been modified. A simple improvement is to move the check inside the previous condition and tweak things a bit more to only increment when needed too:

template<typename RandomAccessIterator>
auto real_index(RandomAccessIterator first, RandomAccessIterator last,
                const std::vector<bool>& sorted, std::size_t n)
    -> RandomAccessIterator
{
    // Number of encountered elements not already sorted
    std::size_t unsorted = 0;

    for (std::size_t i = 0 ; i < sorted.size() ; ++i)
    {
        if (not sorted[i])
        {
            if (unsorted == n)
            {
                return std::next(first, i);
            }
            ++unsorted;
        }
    }
    return last;
}

I also decided to use std::next to make it obvious what's an iterator and what's not.

Sort before, move next

@JS1's idea was the good one: instead of performing a slow lookup on the fly to find the next element to move, it's better to copy all the iterators once and perform a \$O(n \log n)\$ sort (std::sort for example) with a specific comparison function that compares to iterators with the value they point to, and fetch the positions in this array.

However, it changes the logic from "where do I go?" to "who goes there?" during the cycles. That said, it avoids having to store a stack of iterators, so the memory used by the algorithm corresponds to \$n\$ iterators and \$n\$ booleans (instead of \$n\$ booleans and at most \$n\$ iterators).

Moreover, it is easy to replace std::sort by any other sorting algorithm to sort the iterators, making it possible to make the algorithm trivially stable if needed.

It's a different algorithm

While the algorithm builds upon cycle sort and Exact-Sort, in the end the only similarities of the final algorithm are the cycle logic and the array of booleans. The complexity has changed, the space complexity has changed, and even the goal has changed: instead of minimizing the number of writes to the original collection (useful for Flash memory for example), this algorithm tries to minimize the number of times the objects from the original collection are moved, even to a temporary variable (Exact-Sort's goal seemed to be close when it talked about fridges though).

As mentioned in a note at the bottom of the original question, I have finally decided to give a new name to the algorithm: I named it mountain sort because it's the algorithm you would use if you needed to sort an actual range of mountain by height, where storing and comparing heights costs nothing but moving a mountain, even to a temporary location, is really expensive.

While I don't provide the full implementation of this new algorithm in this answer, you can find it on GitHub with more or less the same comments.