Vergesort — A runs-adaptive layer to enhance sorting algorithms

Question

More than a full-fledged sorting algorithm, vergesort is a Runs-adaptive algorithm that falls back most of the time to another sorting algorithm to sort a sequence of elements, but is able to identify ascending or descending runs (already sorted subsequences) in the sequence to sort and to take advantage of them to perform fewer operations.

While vergesort shares similarities with NeatSort (even though I had no knowledge of it when creating vergesort), the latter is a full-fledged sorting algorithm, not a mere optimization layer above other sorting algorithms. Moreover, I didn't put as much thought in the merge phase as NeatSort did.

The algorithm

I'm a bit lazy, so here is a copy-paste of the description from the repository:

Vergesort is based on a very simple principle: it tries to find big runs in the collection to sort to take advantage of the presortedness, and falls back to another sorting algorithm to handle the sections of the collection to sort without big enough runs. Its best feature is its ability to give up really fast in most scenarios and to fallback to another sorting algorithm without a noticeable overhead. More than a sorting algorithm, it's a thin layer to add on top of other sorting algorithms.

Basically, vergesort runs through the collection while it is sorted in ascending or descending order, and computes the size of the current run. If the run is big enough, then vergesort remembers the bounds of the run to merge it in another step (it reverses the run first if it is sorted in descending order). If the run is not big enough, vergesort just remembers its beginning and moves on to the next run. When it reaches a big enough run, it calls the fallback sorting algorithm to sort every element between the beginning of the section without big enough runs and the beginning of the current big enough run.

Once vergesort has crossed the entire collection, there should only be fairly big sorted runs left. At this point, vergesort uses a \$k\$-way merge to merge all the runs and leave a fully sorted collection.

A run is considered big enough when its size is bigger than \$\frac{n}{\log{n}}\$, where \$n\$ is the size of the entire collection to sort. This heuristic is sometimes suboptimal since tests have proven that it would be better not to fall back to the underlying sorting algorithm in some cases, but I was unable to find a better general-purpose heuristic, so this one will do for the time being.

Of course I'm still lazy, so here is a copy-paste of the description of the main optimization of vergesort:

Vergesort has one main optimization which allows to scan the collection for big enough runs and to fail fast enough that it is almost unnoticeable in the benchmarks: instead of going through the collection element by element, vergesort jumps \$\frac{n}{\log{n}}\$ elements at a time, and expands iterators to the left and to the right to check whether it is in a big enough run. In some cases, it allows to detect that we are not in a big enough run without having to check every element and to fall back to the pattern-defeating quicksort with barely more than \$\log{n}\$ comparisons. This optimization requires jumps through the table and thus requires random-access iterators.

The complexity

I won't repeat the whole complexity analysis (you can find it in the repository's README), but the complexity of the algorithm depends on whether there is extra memory available (because the merging step relies on std::inplace_merge):

• If extra memory is available, vergesort is \$O(n \log{n})\$
• Otherwise it is \$O(n \log{n} \log{\log{n}})\$

Vergesort always requires up to \$O(\log{n})\$ extra memory to keep track of the runs, but may use up to \$O(n)\$ extra memory (if available) for the merge operations.

The sexy implementation you were all waiting for

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

// Returns floor(log2(n)), assumes n > 0
template<typename Integer>
auto log2(Integer n)
    -> Integer
{
    Integer log = 0;
    while (n >>= 1) {
        ++log;
    }
    return log;
}

template<typename RandomAccessIterator, typename Compare=std::less<>>
auto vergesort(RandomAccessIterator first, RandomAccessIterator last, Compare compare={})
    -> void
{
    using difference_type = typename std::iterator_traits<RandomAccessIterator>::difference_type;
    difference_type dist = std::distance(first, last);

    if (dist < 128) {
        // Vergesort is inefficient for small collections
        std::sort(std::move(first), std::move(last), std::move(compare));
        return;
    }

    // Limit under which std::sort is used to sort a sub-sequence
    const difference_type unstable_limit = dist / log2(dist);

    // Vergesort detects big runs in ascending or descending order,
    // and remember where each run ends by storing the end iterator
    // of each run in this list, then it merges everything in the end
    std::list<RandomAccessIterator> runs;

    // Beginning of an unstable partition, or last if the previous
    // partition is stable
    auto begin_unstable = last;

    // Pair of iterators to iterate through the collection
    auto current = first;
    auto next = std::next(first);

    while (true) {
        // Beginning of the current sequence
        auto begin_range = current;

        // If the last part of the collection to sort isn't
        // big enough, consider that it is an unstable sequence
        if (std::distance(next, last) <= unstable_limit) {
            if (begin_unstable == last) {
                begin_unstable = begin_range;
            }
            break;
        }

        // Set backward iterators
        std::advance(current, unstable_limit);
        std::advance(next, unstable_limit);

        // Set forward iterators
        auto current2 = current;
        auto next2 = next;

        if (compare(*next, *current)) {
            // Found a decreasing sequence, move iterators
            // to the limits of the sequence
            do {
                --current;
                --next;
                if (compare(*current, *next)) break;
            } while (current != begin_range);
            if (compare(*current, *next)) ++current;

            ++current2;
            ++next2;
            while (next2 != last) {
                if (compare(*current2, *next2)) break;
                ++current2;
                ++next2;
            }

            // Check whether we found a big enough sorted sequence
            if (std::distance(current, next2) >= unstable_limit) {
                std::reverse(current, next2);
                if (std::distance(begin_range, current) && begin_unstable == last) {
                    begin_unstable = begin_range;
                }
                if (begin_unstable != last) {
                    std::sort(begin_unstable, current, compare);
                    runs.push_back(current);
                    begin_unstable = last;
                }
                runs.push_back(next2);
            } else {
                // Remember the beginning of the unsorted sequence
                if (begin_unstable == last) {
                    begin_unstable = begin_range;
                }
            }
        } else {
            // Found an increasing sequence, move iterators
            // to the limits of the sequence
            do {
                --current;
                --next;
                if (compare(*next, *current)) break;
            } while (current != begin_range);
            if (compare(*next, *current)) ++current;

            ++current2;
            ++next2;
            while (next2 != last) {
                if (compare(*next2, *current2)) break;
                ++current2;
                ++next2;
            }

            // Check whether we found a big enough sorted sequence
            if (std::distance(current, next2) >= unstable_limit) {
                if (std::distance(begin_range, current) && begin_unstable == last) {
                    begin_unstable = begin_range;
                }
                if (begin_unstable != last) {
                    std::sort(begin_unstable, current, compare);
                    runs.push_back(current);
                    begin_unstable = last;
                }
                runs.push_back(next2);
            } else {
                // Remember the beginning of the unsorted sequence
                if (begin_unstable == last) {
                    begin_unstable = begin_range;
                }
            }
        }

        if (next2 == last) break;

        current = std::next(current2);
        next = std::next(next2);
    }

    if (begin_unstable != last) {
        // If there are unsorted elements left, sort them
        runs.push_back(last);
        std::sort(begin_unstable, last, compare);
    }

    if (runs.size() < 2) return;

    // Merge runs pairwise until there aren't runs left
    do {
        auto begin = first;
        for (auto it = runs.begin() ; it != runs.end() && it != std::prev(runs.end()) ; ++it) {
            std::inplace_merge(begin, *it, *std::next(it), compare);

            // Remove the middle iterator and advance
            it = runs.erase(it);
            begin = *it;
        }
    } while (runs.size() > 1);
}

Missed optimizations

I tried to keep the code above simple enough, without too many subtle tricks. Here are a few potential optimizations that I didn't implement:

• Reimplementing inplace_merge would allow to reuse the merge memory instead of allocating and deallocating memory for each inplace_merge call. However, I had problems with my benchmarks when I tried to do so, probably due to heap fragmentation or something like that.
• To reduce the memory used by std::inplace_merge, one could use std::lower_bound and std::upper_bound on two runs before merging them to find the values that will stay in place anyway, and thus reduce the merge domain.
• Internal buffering could also sometimes be used to avoid having to allocate memory to perform the merge operations, but that would complicate the structure of the algorithm.
• Another merging strategy such as the ping-pong merge from Ping-Pong Patience+ Sort, or the enhanced pairwis merging strategy used by NeatSort may yield better results than the basic pairwise merge currently used by vergesort.
• Vergesort currently only considers equal values as part of an ascending run. In some cases, it might be more interesting to consider such values to be part of a descending run. That said, the logic to decide which is better could become rather complicated.

As you can see, these missed optimizations are mostly about the merging strategy. But most of the time when merging is needed, the overall running time of the algorithm is already lower than that of the fallback algorithm, so we're already winning, and making the merge step more complicated wouldn't buy us that much more.

The end word

I used std::sort as a fallback for this question to make things simpler, but the repository version falls back to a pattern-defeating quicksort instead.

Anyway, the fallback sorting algorithm used does not matter that much considering that vergesort's goal is to be a cheap optimization above that fallback. Most sorting algorithms can be used as fallbacks as can be seen in these benchmarks.

I guess that it's pretty much it. Do you have any remark about things that could be improved, be it from a correctness, performance, or style point of view? :)

Answer 1

Your implementation consistently uses trailing return type specification even when not needed, hopefully to look more sexy. Personally, I don't like it, but sexiness is subjective.

The log2 function can be made constexpr (thus noexcept), and Integer should be constrained. Also, assumes n > 0 may deserve an assertion. Like this:

template <typename Integer,
          std::enable_if_t<std::is_integral<Integer>::value, int> = 0>
constexpr Integer log2(Integer n)
{
    assert(n > 0);
    // ...
}

Also, the name log2 is likely to cause a name clash. We have log2 in the standard library.

Since C++20, the log2 function can be simplified:

template <std::Integral Integer>
constexpr Integer log2(Integer n)
{
    assert(n > 0);
    return std::log2p1(static_cast<std::make_unsigned_t<Integer>>(n)) - 1;
}

(You will need #include <concept> and #include <bit>.)

RandomAccessIterator is an incredibly long names. This is unnecessary. Use a shorter name like RanIt.

Similarly, vergesort may also benefit from constraint. Currently, the vergesort function is way too long. It should definitely be broken up to logical parts. Also, uses a std::list to handle the runs. You probably chose it based on benchmarks, but it is definitely better to provide an interface to customize. You can take a buffer template parameter:

template </* same as before */, typename Buffer = std::list<RanIt>>

Also, there is the (extremely unlikely) edge-case of difference_type being unable to hold such a "big" number as 128.