3
\$\begingroup\$

As the title says, I'm trying to implement a merge sort algorithm in C++ that's also adaptive. This is a personal exercise, and I don't have any specific application in mind. My main goal is to write something that's succinct and easy to understand but also has reasonably good performance.

I'm aware that implementations already exist: TimSort (C++ implementation), for example. And new enough versions of GCC's C++ library seem to implement std::stable_sort using an adaptive algorithm as well. I'm not looking to replace either of these, or beat them in performance (though I would be happy if I came close).

So here is what I have. I'd be particularly interested to know of any bugs/special cases I've missed, or opportunities to improve the performance without increasing the complexity/code size too much. I've also tried to make good use of C++11 features (other than, of course, std::stable_sort itself), and if there are improvements that could be made on that front, I'd like to know as well.

#include <algorithm>
#include <iterator>
#include <vector>

/*
 * This algorithm borrows some ideas from TimSort but is not quite as
 * sophisticated.  Runs are detected, but only in the forward direction, and the
 * invariant is stricter: each stored run must be no more than half the length
 * of the previous.
 *
 * As in TimSort, an already-sorted array will be processed in linear time,
 * making this an "adaptive" algorithm.
 */

template<typename Iter, typename Less>
class MergeSort
{
private:
    typedef typename std::iterator_traits<Iter>::value_type Value;
    typedef typename std::vector<Value>::size_type Size;

    /* Inserts a single element into a sorted list */
    static void insert_head (Iter head, Iter tail, Less less)
    {
        Iter dest;

        for (dest = head + 1; dest + 1 < tail; dest ++)
        {
            if (! less (* (dest + 1), * head))
                break;
        }

        Value tmp = std::move (* head);
        std::move (head + 1, dest + 1, head);
        * dest = std::move (tmp);
    }

    /* Merges two sorted sub-lists */
    static void do_merge (Iter head, Iter mid, Iter tail, Less less, std::vector<Value> & buf)
    {
        /* copy list "a" to temporary storage */
        if (buf.size () < (Size) (mid - head))
            buf = std::vector<Value> (std::make_move_iterator (head), std::make_move_iterator (mid));
        else
            std::move (head, mid, buf.begin ());

        auto a = buf.begin ();
        auto a_end = a + (mid - head);
        Iter b = mid;
        Iter dest = head;

        while (1)
        {
            if (! less (* b, * a))
            {
                * (dest ++) = std::move (* a);
                if ((++ a) == a_end)
                    break;
            }
            else
            {
                * (dest ++) = std::move (* b);
                if ((++ b) == tail)
                    break;
            }
        }

        /* copy remainder of list "a" */
        std::move (a, a_end, dest);
    }

public:
    /* Top-level merge sort algorithm */
    static void sort (Iter start, Iter end, Less less)
    {
        /* A list with 0 or 1 element is sorted by definition. */
        if (end - start < 2)
            return;

        std::vector<Value> buf;

        /* The algorithm runs right-to-left (so that insertions are left-to-right). */
        Iter head = end;

        /* Markers recording the divisions between sorted sub-lists or "runs".
         * Each run is at least 2x the length of its left-hand neighbor, so in
         * theory a list of 2^64 - 1 elements will have no more than 64 runs. */
        Iter div[64];
        int n_div = 0;

        do
        {
            Iter mid = head;
            head --;

            /* Scan right-to-left to find a run of increasing values.
             * If necessary, use insertion sort to create a run at 4 values long.
             * At this scale, insertion sort is faster due to lower overhead. */
            while (head > start)
            {
                if (less (* head, * (head - 1)))
                {
                    if (mid - head < 4)
                        insert_head (head - 1, mid, less);
                    else
                        break;
                }

                head --;
            }

            /* Merge/collapse sub-lists left-to-right to maintain the invariant. */
            while (n_div >= 1)
            {
                Iter tail = div[n_div - 1];

                while (n_div >= 2)
                {
                    Iter tail2 = div[n_div - 2];

                    /*
                     * Check for the occasional case where the new sub-list is
                     * longer than both the two previous.  In this case, a "3-way"
                     * merge is performed as follows:
                     *
                     *   |---------- #6 ----------|- #5 -|---- #4 ----| ...
                     *
                     * First, the two previous sub-lists (#5 and #4) are merged.
                     * (This is more balanced and therefore more efficient than
                     * merging the long #6 with the short #5.)
                     *
                     *   |---------- #5 ----------|-------- #4 -------| ...
                     *
                     * The invariant guarantees that the newly merged sub-list (#4)
                     * will be shorter than its right-hand neighbor (#3).
                     *
                     * At this point we loop, and one of two things can happen:
                     *
                     *  1) If sub-list #5 is no longer than #3, we drop out of the
                     *     loop.  #5 is still longer than half of #4, so a 2-way
                     *     merge will be required to restore the invariant.
                     *
                     *  2) If #5 is longer than even #3 (rare), we perform another
                     *     3-way merge, starting with #4 and #3.  The same result
                     *     holds true: the newly merged #3 will again be shorter
                     *     than its right-hand neighbour (#2).  In this fashion the
                     *     process can be continued down the line with no more than
                     *     two sub-lists violating the invariant at any given time.
                     *     Eventually no more 3-way merges can be performed, and the
                     *     invariant is restored by a final 2-way merge.
                     */

                    if ((mid - head) <= (tail2 - tail))
                        break;

                    do_merge (mid, tail, tail2, less, buf);

                    tail = tail2;
                    n_div --;
                }

                /*
                 * Otherwise, check whether the new sub-list is longer than half its
                 * right-hand neighbour.  If so, merge the two sub-lists.  The
                 * merged sub-list may in turn be longer than its own right-hand
                 * neighbor, and if so the entire process is repeated.
                 *
                 * Once the "head" pointer reaches the beginning of the original
                 * list, we simply keep merging until only one sub-list remains.
                 */

                if (head > start && (mid - head) <= (tail - mid) / 2)
                    break;

                do_merge (head, mid, tail, less, buf);

                mid = tail;
                n_div --;
            }

            /* push the new sub-list onto the stack */
            div[n_div] = mid;
            n_div ++;
        }
        while (head > start);
    }
};

template<typename Iter, typename Less>
void mergesort (Iter start, Iter end, Less less)
    { MergeSort<Iter, Less>::sort (start, end, less); }

template<typename Iter>
void mergesort (Iter const start, Iter const end)
{
    typedef typename std::iterator_traits<Iter>::value_type Value;
    mergesort (start, end, std::less<Value> ());
}

GitHub repository: https://github.com/jlindgren90/mergesort

\$\endgroup\$
4
\$\begingroup\$

Design

A class with all static members! Seems like the wrong use case. We have namespace for that type of thing.

Code Review

I like the comment at the top:

/*
 * This algorithm borrows some ideas from TimSort but is not quite as
 * sophisticated.  Runs are detected, but only in the forward direction, and the
 * invariant is stricter: each stored run must be no more than half the length
 * of the previous.
 *
 * As in TimSort, an already-sorted array will be processed in linear time,
 * making this an "adaptive" algorithm.
 */

Though I am unfamiliar with TimSort it easy to google. So a very nice comment all in all.

I hate this comment though:

    /* Inserts a single element into a sorted list */
    static void insert_head (Iter head, Iter tail, Less less)

Especially when it does not seem to match the function. What element is being inserted here? After reading the code it seems like the element at the head of the range is sorted into place as the elements [head + 1 to tail) are already sorted.

Better name better comment on what it does. Preferably just a better function name.

Not all iterators support + operation or the < operation. This is why we have std::next or operator++ and iterators are usually tested with != or ==. Also, it looks like you are just doing a std::find_if(), so use the algorithm.

        for (dest = head + 1; dest + 1 < tail; dest ++)
        {
            if (! less (* (dest + 1), * head))
                break;
        }

        // I would rewrite as:
        I loop = head;
        ++loop;
        auto find = std::find_if(loop, tail, [&less](I lhs, I rhs){return  !less(*lhs, *rhs);});

This bit of code:

        Value tmp = std::move (* head);
        std::move (head + 1, dest + 1, head);
        * dest = std::move (tmp);

is implemented by std::rotate().

Again I hate the comment. Not because it or the function are badly named. But because the comment does not give me any extra information. If it is not giving me information, it is actually worse than nothing as it will suffer from comment rot over time. The name of the function and its parameters should be your documentation.

    /* Merges two sorted sub-lists */
    static void do_merge (Iter head, Iter mid, Iter tail, Less less, std::vector<Value> & buf)

Using the operator - on iterators is not always supported. You should use std::distance(). Also using a C-cast is not tolerated in any civilized world. Take your heathen ways and reform, sinner! C++ has its own set of cast operators that do this much better. In this case static_cast<>(). But if you use std::distance() you don't need it.

Very clever. So clever I had to go through it a couple of times to convince myself it worked. This is where you may want to comment on being clever.

        /* copy list "a" to temporary storage */
        if (buf.size () < (Size) (mid - head))
            buf = std::vector<Value> (std::make_move_iterator (head), std::make_move_iterator (mid));
        else
            std::move (head, mid, buf.begin ());

But a vector contains two sizes: size() and capacity(). There is no need to allocate a new vector just because the size has been exceeded: you can go until you reach capacity. But even then, why are you doing it manually? The vector is designed to do this stuff all internally in the most efficient way. You should just copy using move iterators and a back inserter. Let the vector sort out its own resizing (this will be usually be more efficient).

        buf.clear();
        std::copy(std::make_move_iterator(head), std::make_move_iterator(mid),
                  std::back_inserter(buf));

Using move iterators and correctly sizing the buffer will make the following code cleaner.

        auto a = buf.begin ();
        auto a_end = a + (mid - head);
        Iter b = mid;
        Iter dest = head;

Sure but this can be made much more readable:

        while (1)
        {
            if (! less (* b, * a))
            {
                * (dest ++) = std::move (* a);
                if ((++ a) == a_end)
                    break;
            }
            else
            {
                * (dest ++) = std::move (* b);
                if ((++ b) == tail)
                    break;
            }
        }

        // I would write it like this:
        while(a != a_end && b != tail) {
            *dest++ = (! less (* b, * a))
                   ? std::move(*a++);
                   : std::move(*b++);
        }

OK. That's enough for one season. Seems like plenty that needs to be re-worked already.

\$\endgroup\$
  • \$\begingroup\$ I like a lot of your suggestions! Especially using std::find_if and std::rotate. I come from a C background so I sometimes forget that algorithms like that are already provided. \$\endgroup\$ – John Lindgren Feb 21 at 3:45
  • \$\begingroup\$ A couple of the things you pointed out that could be simplified (like using std::back_inserter, or writing the merge loop more compactly) I did already try, but found that GCC didn't optimize those forms as well. I'll re-examine those, and if there's no way to simplify them without losing performance, I'll add comments explaining why they are the way they are. \$\endgroup\$ – John Lindgren Feb 21 at 3:48
  • \$\begingroup\$ @JohnLindgren Don't get fooled by micro optimizations. The majority of the time spent on by code is on writing and maintaining. Saving a couple of micro seconds a year is not worth the maintenance cost in the next person having to understand the code. Optimizations should be done at the algorithm level. \$\endgroup\$ – Martin York Feb 21 at 14:22
  • \$\begingroup\$ Agreed, generally speaking ... but seeing that I'm already writing my own sort algorithm rather than using std::stable_sort, you can assume that reducing maintenance time is not my primary goal in this exercise :) My rule of thumb here is, if increasing the code size by 5% results in a >5% performance gain, I'll do it. \$\endgroup\$ – John Lindgren Feb 21 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.