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:
- 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.
- Then it sorts the elements that are not part of the LNDS.
- 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 :)
