QuickMergesort — The power of internal buffering

Question

Amongst the lesser-known unstable sorting algorithms is the QuickXsort family of algorithms, as described in QuickXsort: Efficient Sorting with n log n - 1.399n +o(n) Comparisons on Average by Stefan Edelkamp and Armin Weiß. This family of sorting algorithms tries to exploit the technique of internal buffering that we will describe below before presenting our algorithm.

Internal buffering & QuickXsort

Internal buffering is a technique which allows to use algorithms that generally need additional memory without actually having to use any additional memory: when applying an algorithm to a sequence of elements, one can decide that the algorithm will first operate on a part of the sequence, and use the other part as a « buffer » with which it will swap elements instead of storing them in additional memory and retrieving them later. Then it can operate on the remaining part of the sequence until completion. Algorithms such as block sort use internal buffering to avoid allocating extra memory.

QuickXsort is a family of algorithms designed to take advantage of quicksort and internal buffering as follows:

• Choose a pivot and partition the original sequence, leaving two partitions A and B.
• If possible, apply another sorting algorithm that generally requires additional memory (such as mergesort) on the biggest partition, and use the second partition as an internal buffer: considering that A is the biggest partition, it can swap elements with B instead of allocating temporary memory to store the values and retrieve them back in A.
• Apply the technique again on the remaining partition until the original sequence is sorted.

Quicksort partitions are an excellent choice here: once a sequence is partitioned, sorting both halves yields a sorted sequence, so any sorting algorithm can be used, and using one of the unsorted partitions as an internal buffer isn't a problem since it isn't supposed to be sorted yet.

QuickMergesort

QuickMergesort applies a partition just like quicksort on the whole sequence, then applies mergesort as follows:

We sort the larger half of the partitioned array with Mergesort as long as we have one third of the whole array as temporary memory left, otherwise we sort the smaller part with Mergesort.

As we can see from the explanation, mergesort can only be used to sort the bigger partition if the smaller partition is at least one third of the sequence to sort. It's that way because mergesort needs a buffer whose size is up to half the size of the sequence to sort (the bigger partition).

A new flavour of QuickMergesort

Instead of partitioning the original sequence with a usual median-of-three pivot selection, I decided that I could use std::nth_element instead for the partition step, always choosing a pivot that splits the sequence to sort into two partitions whose sizes are respectively two thirds and one third of the size of the partition to sort. That way, it ensures that mergesort can be performed on the biggest possible partition at each step.

For the sake of simplicity, we use an almost trivial top-down mergesort that switches to an insertion sort when there are fewer than 32 elements. Anyway, we've talked enough, here is the code:

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

// Number of elements to sort under which we perform insertion sort
static constexpr int insertion_limit = 32;

template<
    typename BidirectionalIterator,
    typename Compare = std::less<>
>
auto insertion_sort(BidirectionalIterator first, BidirectionalIterator last,
                    Compare compare={})
    -> void
{
    if (first == last) return;

    for (BidirectionalIterator cur = std::next(first) ; cur != last ; ++cur) {
        BidirectionalIterator sift = cur;
        BidirectionalIterator sift_1 = std::prev(cur);

        // Compare first so we can avoid 2 moves for
        // an element already positioned correctly.
        if (compare(*sift, *sift_1)) {
            auto tmp = std::move(*sift);
            do {
                *sift-- = std::move(*sift_1);
            }
            while (sift != first && compare(tmp, *--sift_1));
            *sift = std::move(tmp);
        }
    }
}

template<
    typename InputIterator1,
    typename InputIterator2,
    typename OutputIterator,
    typename Compare = std::less<>
>
auto half_inplace_merge(InputIterator1 first1, InputIterator1 last1,
                        InputIterator2 first2, InputIterator2 last2,
                        OutputIterator result, Compare compare={})
    -> void
{
    for (; first1 != last1; ++result) {
        if (first2 == last2) {
            std::swap_ranges(first1, last1, result);
            return;
        }

        if (compare(*first2, *first1)) {
            std::iter_swap(result, first2);
            ++first2;
        } else {
            std::iter_swap(result, first1);
            ++first1;
        }
    }
    // first2 through last2 are already in the right spot
}

template<
    typename BidirectionalIterator,
    typename Compare = std::less<>
>
auto buffered_inplace_merge(BidirectionalIterator first, BidirectionalIterator middle,
                            BidirectionalIterator last, BidirectionalIterator buffer,
                            Compare compare={})
    -> void
{
    if (middle - first <= last - middle) {
        auto buffer_end = std::swap_ranges(first, middle, buffer);
        half_inplace_merge(buffer, buffer_end,
                           middle, last,
                           first, compare);
    } else {
        auto buffer_end = std::swap_ranges(middle, last, buffer);
        using rev_iter = std::reverse_iterator<BidirectionalIterator>;
        half_inplace_merge(rev_iter(buffer_end), rev_iter(buffer),
                           rev_iter(middle), rev_iter(first), rev_iter(last),
                           std::not_fn(compare));
    }
}

template<
    typename BidirectionalIterator,
    typename Compare = std::less<>
>
auto internal_mergesort(BidirectionalIterator first, BidirectionalIterator last,
                        BidirectionalIterator buffer, Compare compare={})
    -> void
{
    if (std::distance(first, last) <= insertion_limit) {
        insertion_sort(first, last, compare);
        return;
    }

    auto middle = first + (last - first) / 2; // make sure left is smaller
    internal_mergesort(first, middle, buffer, compare);
    internal_mergesort(middle, last, buffer, compare);

    while (first != middle && not compare(*middle, *first)) {
        ++first;
    }
    if (first == middle) return;

    buffered_inplace_merge(first, middle, last, buffer, compare);
}

template<
    typename RandomAccessIterator,
    typename Compare = std::less<>
>
auto quickmergesort(RandomAccessIterator first, RandomAccessIterator last,
                    Compare compare={})
    -> void
{
    auto size = std::distance(first, last);
    while (size > insertion_limit) {
        auto pivot = first + 2 * (size / 3) - 2;
        std::nth_element(first, pivot, last, compare);
        internal_mergesort(first, pivot, pivot, compare);

        first = pivot;
        size = std::distance(first, last);
    }
    insertion_sort(first, last, compare);
}

The original version of insertion_sort comes from Orson Peters' pdqsort; the original versions from half_inplace_merge and buffered_inplace_merge come from libc++'s implementation of std::inplace_merge. They have been adapted for the purpose of internal buffering.

Complexity and performance

std::nth_element runs in \$\mathcal{O}(n)\$, and top-down mergesort in \$\mathcal{O}(n \log{n})\$. To be honest, I don't know whether the whole thing actually runs in \$\mathcal{O}(n \log{n})\$ or in \$\mathcal{O}(n \log^{2}{n})\$. I'd say \$\mathcal{O}(n \log{n})\$, but then again I'm not sure. Since I choose to use a top-down mergesort for the sake of simplicity, the algorithm takes \$\mathcal{O}(\log{n})\$ space, but it could use \$\mathcal{O}(1)\$ space with a bottom-up mergesort.

I didn't run benchmarks in a while, but the algorithm seemed to run more or less as fast as libstdc++ std::sort (which implements an introsort, at least at the time of benchmarks), except in a few situations: it's a bit slower for truly random data and when there's only a small number of different elements, and it's way better for std::sort's worst distributions (when it falls back to heapsort). It's almost always twice as fast as heapsort.

The only benchmarks I have were performed on a vector of 10⁶ integers though. Its running time is probably different in other situations.

Conclusions

I think that the algorithm is quite elegant and rather fast without being too clever for its own good, and a is pretty good example of what can be done with internal buffering without being as complex as a block sort. It also allowed me to finally find a good use for std::nth_element (I was pretty disappointed by the speed of the \$\mathcal{O}(n \log{n})\$ quicksort that uses std::nth_element for its partitioning step), which is also quite nice :)

As usual, do you think that something could obviously be improved with this code, be it from a coding style, performance, elegance of correctness perspective (that said, note that some things have been simplified for Code Review, such as the lack of a namespace to hide the internals)?

Answer 1

I realized that at least two things could be simplified since asking the question.

half_inplace_merge takes only one kind of iterators

The function half_inplace_merge was borrowed from libc++'s implementation of std::inplace_merge. However, despite its name, std::inplace_merge might allocate additional memory to perform an out-of-place merge when possible, so when half_inplace_merge is called, it's sometimes with different kinds of iterators.

However, in our case, the merge is always internal, and swaps elements in the same collection, so the iterators are always the same. We can thus simplify the signature of half_inplace_merge as follows:

template<
    typename InputIterator,
    typename OutputIterator,
    typename Compare = std::less<>
>
auto half_inplace_merge(InputIterator first1, InputIterator last1,
                        InputIterator first2, InputIterator last2,
                        OutputIterator result, Compare compare={})
    -> void
{
    // ...
}

It doesn't seem to incur any additional performance cost or benefit, but it makes the code simpler and cleaner.

The left partition is always smaller

In libc++'s implementation of std::inplace_merge, the left and right partitions to merge in a sequence could have any size, so the check to know which of the partitions was smaller was necessary to always make the best of the algorithm.

However, in our case, the sequence to mergesort is always split in two parts, the first one always being the smaller one. Moreover, an additional trick is used to shrink the left partition, making it even smaller, without having any effect on the size of the right partition. In the end, when buffered_inplace_merge is called, the left partition is always smaller than the right one, and makes the check useless. The function can be simplified as follows:

template<
    typename ForwardIterator,
    typename Compare = std::less<>
>
auto buffered_inplace_merge(ForwardIterator first, ForwardIterator middle,
                            ForwardIterator last, ForwardIterator buffer,
                            Compare compare={})
    -> void
{
    auto buffer_end = std::swap_ranges(first, middle, buffer);
    half_inplace_merge(buffer, buffer_end,
                       middle, last,
                       first, compare);
}

Note that dropping the reverse iterators lowered the iterator requirements of the function to forward iterators, even though the overall quick_merge_sort still requires random-access iterators because of std::nth_element.

Dropping std::not_fn also means that the code doesn't use any C++17 feature anymore and works out-of-the-box with a C++14 compiler. Sure, it could be made to work with even C++03, but that's not the point :)

Avoid a gratuitous albeit small pessimization when sorting an std::deque

The following line will likely perform a few extra operations if we try to sort an std::deque with quickmergesort:

auto pivot = first + 2 * (size / 3) - 2;

Since operator+ is left-associative, the statement above is equivalent to the following one:

auto pivot = (first + 2 * (size / 3)) - 2;

When first is an std::deque iterator, it is first incremented by first + 2 * (size / 3), then decremented by 2. Considering that operator+ and operator- are not trivial for std::deque iterators, computing 2 * (size / 3) - 2 then incrementing first is likely more efficient. We can thus avoid this small albeit gratuitous pessimization by transforming the statement as follows:

auto pivot = first + (2 * (size / 3) - 2);

In this specific algorithm, it should not make a noticeable difference, but some algorithms can become dramatically faster with std::deque (and other random-access containers with not-trivial logic) when making sure that we are avoiding such pessimizations.