SplitSort — An adaptive algorithm to handle collections with few inversions

Question

SplitSort

SplitSort is a rather simple Inv-adaptive and Rem-adaptive sorting algorithm described in Splitsort — an adaptive sorting algorithm by Christos Levcopoulos and Ola Petersson. The paper actually contains two algorithms: a smart out-of-place version, and a simpler in-place version which removes a few of the algorithm's subtleties in order to make it run without having to allocate additional memory.

SplitSort is a sorting algorithm working in three steps:

1. First it tries to isolate an approximation of a longest non-decreasing subsequence (LNDS) in the collection by splitting the collection in two parts: one with the LNDS and one with the other elements.
2. Then it sorts the elements that are not part of the LNDS.
3. Finally it merges the two parts of the collection.

Instead of trying to find an actual LNDS, the algorithm uses a simple heuristic to find an approximate LNDS: it reads the collection element per element and considers every element found so far to be part of the LNDS, but whenever it reads an element which is strictly smaller than the previous one, it removes both elements from the approximate LNDS.

In order to implement that as an in-place algorithm, the following technique is used: an iterator points to the next element to read, and another iterator points to the last element which is part of the approximate LNDS; both pointers are increased as long as the elements read are part of the approximate LNDS and the latest read value is swapped with the element right after the head of the approximate LNDS. Whenever two elements need to be dropped, the iterator pointer to the head of the LNDS is decremented and the reader iterator is still increased. Once the whole collection has been crossed by the reader iterator, the resulting collection should have roughly the following shape:

[ LNDS | unsorted elements ]

The only thing left to do is to sort the unsorted elements and to merge the two parts of the collection in order to obtained a fully sorted collection.

The code

#include <algorithm>
#include <functional>
#include <iterator>
#include <utility>

template<typename RandomAccessIterator, typename Compare=std::less<>>
auto split_sort(RandomAccessIterator first, RandomAccessIterator last, Compare compare={})
    -> void
{
    if (std::distance(first, last) < 2) return;

    // Read elements and build the LNDS
    auto middle = first; // Last element of the LNDS
    for (auto reader_it = std::next(first) ; reader_it != last ; ++reader_it) {
        if (compare(*reader_it, *middle)) {
            // We remove the top of the subsequence as well as the new element
            if (middle != first) {
                --middle;
            }
        } else {
            // Everything is fine, add the new element to the subsequence
            ++middle;
            std::iter_swap(middle, reader_it);
        }
    }

    std::sort(middle, last, compare);
    std::inplace_merge(first, middle, last, compare);
}

Performance

As a bonus, here is a graph showing the performance of SplitSort against two other sorting algorithms when sorting collections of \$ 10^5 \$ long std::string with an increasing number of out-of-place elements:

It's a bit sketchy but we can see that SplitSort performs better than pdqsort (a smart introsort derivative) when under 40% of the elements are out-of-place and has some additional overhead when more elements are out-of-place. I also included drop-merge-sort in the benchmark because it uses a technique really similar to SplitSort except that it uses a smarter LNDS approximation scheme, and also isn't an in-place algorithm contrary to SplitSort. We can see that both algorithms offer a different trade-off with drop-merge-sort being faster than SplitSort when there aren't many out-of-place elements, but having a higher overhead when there are more such elements. Interestingly enough, both algorithms have a cut-off point around 40% of out-of-place elements where they start to perform worse than an introsort-like algorithm.

Conclusion

That's it, now you know how to write a simple algorithm to sort collections with few out-of-place elements faster. Any suggestion about improving the code so that it's more performant or more readable is welcome :)

Answer 1

There is nothing wrong that I can see.

I can nitpick (so this is only to be overly nitpicky). But nothing I say here would stop me from merging this into an existing code base (assuming you had the tests to prove it worked correctly).

1. Your template type RandomAccessIterator indicates you only support random access iterators (RAI). If you absolutely want this to be a RAI then maybe you should enforce it? Does std::sort() enforce that for you? Even if it does is the error messaging a bit obtuse? Ask the question can I help the user of my code spot and diagnose issues more easily if they use it incorrectly?

2. With C++17 std::sort() and std::inplace_merge() support execution policies. Can you work that into your sort? Even if you don't use it yourself can you pass it through to one (or both) of these methods?

3. Find the new return type syntax a bit unnatural still. Personally I only use this when I need to determine the return type at compile time. But don't have anything against it per say.

4. The graph is a bit spikey. I presume that is because of the randomness of the strings you sort. Don't get rid of that but if you supplemented that by assuming one sort is base time and drawing the other two lines as percentage better/worse relative to your reference sort. Does this provide clearer indication of how each sort improves with randomness?

5. Since this is a pretty unique sort. I would add a comment that has a link to the paper describing the sort. Maybe also a link to any graphs documentation you have written (which could be this page).