Modern, C++ compliant, merge sort

Question

This is a kind of follow up to my previous sort implementation review with specific questions to merge sort, and Modern C++ idioms.

template<typename InputIt1,
         typename InputIt2,
         typename OutputIt,
         typename Comparator = std::less<typename std::iterator_traits<InputIt1>::value_type >>
void merge(InputIt1 first1,
           InputIt1 last1,
           InputIt2 first2,
           InputIt2 last2,
           OutputIt out,
           Comparator cmp = Comparator())
{
    while (first1 != last1 || first2 != last2)
    {
        if (first2 == last2 || first1 != last1 && cmp(*first1, *first2))
        {
            *out = *first1++;
        }
        else
        {
            *out = *first2++;
        }
        ++out;
    }
}

template<typename BidirIt,
         typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type >>
void sort_merge(BidirIt first,
                BidirIt last,
                Comparator cmp = Comparator())
{
    typedef std::iterator_traits<BidirIt>::difference_type dt;
    typedef std::iterator_traits<BidirIt>::value_type vt;

    dt size = std::distance(first, last);
    if (size > dt(1))
    {
        auto middle = first + size / dt(2);

        std::vector<vt> left(first, middle);
        std::vector<vt> right(middle, last);

        auto left_begin = left.begin(), left_end = left.end();
        auto right_begin = right.begin(), right_end = right.end();

        sort_merge(left_begin, left_end);
        sort_merge(right_begin, right_end);

        ::merge(left_begin, left_end, right_begin, right_end, first);
    }
}

I am looking for any performance optimizations I may have missed in the algorithm itself, as well as Modern C++ constructs I may not be abiding by for this example.

I looked into in-place merging, however, all of the solutions I have found for in-place merging perform worse. Namely, substituting a sort_insertion for the merge operation. However, if I were to make an in-place sort_merge, I would start a separate topic as it's considered a completely separate algorithm.

Answer 1

Prefer to use move rather than copy semantics

If your object is an int then it makes no difference. But some objects are more expensive to copy (such as std::string). If you can move rather than copy you will get much better performance with more complex objects.

*out = *first1++;

// Just add a call to std::move
*out = std::move(*first1++);

Too many lines of parameters

This is bit difficult to say this is required or perfect and you can make arguments both ways. But one parameter per line seems a bit over verbose. I prefer to group my parameters into logical groups (tools don't like this as they can't apply logical as it is situation specific).

But I personally think that for readability it makes sense to put parameters in logical groups.

(see below)

Member types names

Technically this is illegal:

typedef std::iterator_traits<BidirIt>::difference_type dt;

The compiler can not tell if difference_type is a type or a member variable until it knows the type of BidirIt. So you need to tell it that it is a typename.

typedef typename std::iterator_traits<BidirIt>::difference_type dt;
 //     ^^^^^^^^  required for standards conformance

Type names

Types are important in C++. Try and use names that help identify the type (be a bit verbose). But also it is a sort of convention that user defined types have an initial upper case letter (so that they can be easily spotted from objects).

typedef std::iterator_traits<BidirIt>::difference_type dt;

// Here I did not like the short name:
typedef typename std::iterator_traits<BidirIt>::difference_type DiffType;

Don't pass comparator to merge by value

The merge operation is not supposed to be done in isolation. It is always called from the sort_merge() function. So there is no need to create a comparator for each call to merge() just create it once in sort_merge() and pass by const reference to all calls to merge():

void merge(InputIt1 first1, InputIt1 last1,
           InputIt2 first2, InputIt2 last2,
           OutputIt out,
           Comparator const& cmp)

Non optimal implementation

while (first1 != last1 || first2 != last2)
{
    if (first2 == last2 || first1 != last1 && cmp(*first1, *first2))
    {
        *out = *first1++;
    }
    else
    {
        *out = *first2++;
    }
    ++out;
}

Better to write as this:

// Test your constraints here.
while (first1 != last1 && first2 != last2)
{
    // The comparison test then becomes much simpler.
    *out = std::move(cmp(*first1, *first2)
                         ? *first1++
                         : *first2++);
    ++out;
}
// Then the final optimized copy
// Only one of these loops will execute.
std::move(first1, last1, out);
std::move(first2, last2, out);

Space optimization

Creating the copy in sort_merge()

    std::vector<vt> left(first, middle);
    std::vector<vt> right(middle, last);

Means that you use more memory because you have a copy in this iteration then make a copy in each recursive call below this one and they are all active at the same time.

If you do the recursive sort_merge() in place. Then in the merge() call perform the copy then you get a much better space usage (as you only have one copy at the current iteration active).

Result

You will notice I have slightly altered the merge. We can make several assumptions about the inputs (because it is only called from sort_merge()):

• There is only one type of input iterator.
  • Because we know we are sorting two halves of the same container.
• There is no output iterator
  • as the merge is done in place.
• The comparator does not need a default type.
  • this is done as part of the sort_merge template.
• I don't pass two ranges.
  • I use begin/mid/end

Code: merge

template<typename I, typename Comparator>
void merge(I first, I mid, I last, Comparator const& cmp)
{
    typedef typename std::iterator_traits<I>::difference_type DiffType;
    typedef typename std::iterator_traits<I>::value_type      ValueType;

    DiffType                size1 = std::distance(first, mid);
    DiffType                size2 = std::distance(mid, last);

    std::vector<ValueType>  hold1;
    std::vector<ValueType>  hold2;
    hold1.reserve(size1);
    hold2.reserve(size2);

    std::move(first, mid,  std::back_inserter(hold1));
    std::move(mid,   last, std::back_inserter(hold2));

    auto first1 = std::begin(hold1);
    auto last1  = std::end(hold1);
    auto first2 = std::begin(hold2);
    auto last2  = std::end(hold2);
    auto out    = first;

    while (first1 != last1 && first2 != last2)
    {
        *out = std::move(cmp(*first1, *first2)
                             ? *first1++
                             : *first2++);
        ++out;
    }
    std::move(first1, last1, out);
    std::move(first2, last2, out);
}

Code: sort_merge

template<typename I,
         typename Comparator = std::less<typename std::iterator_traits<I>::value_type>>
void sort_merge(I first,
                I last,
                Comparator cmp = Comparator())
{
    typedef typename std::iterator_traits<BidirIt>::difference_type DiffType;

    DiffType size = std::distance(first, last);
    if (size > DiffType(1))
    {
        auto middle = first + size / 2;
        auto midIter = begin;
        std::advance(midIter, middle);

        sort_merge(first, midIter, cmp);
        sort_merge(midIter, last,  cmp);

        merge(first, midIter, end, cmp);
    }
}

Answer 2

Since I am a beginner C++ programmer, I cannot comment on the way you use the language, but I can suggest performance improvements: in your merge function you create a vector to hold the merged range, merge the two runs into it, and then copy the vector back to the original input array, and that's ain't cool: in the topmost call to your merge sort you could have created a buffer array that you pass to all subsequent merge sort functions. The point here is that the two arrays (buffer and the original input array) alternate their roles; in one merge pass you merge from buffer to original; at the next merge pass you merge from original to buffer. Of course, you can arrange things so that the sorted stuff magically ends up in the original input array. This approach gave me constantly a speed up of 3 compared to your implementation.

Below the small demonstration program:

#include <algorithm>
#include <chrono>
#include <functional>
#include <iostream>
#include <random>

using namespace std;

template<typename BidirIt,
         typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type >>
void sort_merge(BidirIt first,
                BidirIt last,
                Comparator cmp = Comparator())
{
    typedef typename std::iterator_traits<BidirIt>::difference_type dt;
    typedef typename std::iterator_traits<BidirIt>::value_type vt;

    dt size = std::distance(first, last);
    if (size > dt(1))
    {
        auto middle = first + size / dt(2);

        std::vector<vt> left(first, middle);
        std::vector<vt> right(middle, last);

        auto left_begin = left.begin(), left_end = left.end();
        auto right_begin = right.begin(), right_end = right.end();

        sort_merge(left_begin, left_end);
        sort_merge(right_begin, right_end);

        ::merge(left_begin, left_end, right_begin, right_end, first);
    }
}

// 'first' is the begin of the target array
// 'last' is the end of the target array
// 'buffer' is the source array
template<typename BidirIt,
         typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type>>
void sort_merge2_impl(BidirIt first, BidirIt last, BidirIt buffer, Comparator cmp = Comparator())
{
    typedef typename std::iterator_traits<BidirIt>::value_type vt;
    typedef typename std::iterator_traits<BidirIt>::difference_type dt;

    dt size = std::distance(first, last);

    if (size < 2) {
        // Trivially sorted.
        return;
    }

    sort_merge2_impl(buffer, buffer + size / 2, first, cmp);
    sort_merge2_impl(buffer + size / 2, buffer + size, first + size / 2, cmp);

    std::merge(buffer, 
               buffer + size / 2, 
               buffer + size / 2, 
               buffer + size, 
               first,
               cmp);
}

// The entry point into optimized merge sort.
template<typename BidirIt,
         typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type >>
void sort_merge2(BidirIt first,
                 BidirIt last,
                 Comparator cmp = Comparator())
{
    typedef typename std::iterator_traits<BidirIt>::difference_type dt;
    typedef typename std::iterator_traits<BidirIt>::value_type vt;
    dt size = std::distance(first, last);

    if (size > dt(1))
    {
        vt* buffer = new vt[size];
        std::copy(first, last, buffer);
        sort_merge2_impl(first, last, buffer, cmp);
    }
}

static int* get_random_int_array(const size_t length,
                                 const int minimum,
                                 const int maximum,
                                 const unsigned int seed)
{
    std::default_random_engine generator(seed);
    std::uniform_int_distribution<int> distribution(minimum, maximum);

    int* array = new int[length];

    for (size_t i = 0; i < length; ++i)
    {
        array[i] = distribution(generator);
    }

    return array;
}

static unsigned long long get_milliseconds()
{
    return std::chrono::duration_cast<std::chrono::milliseconds>(
           std::chrono::system_clock::now().time_since_epoch()).count();
}

int main(int argc, char** argv) {
    constexpr size_t length = 1000000;

    unsigned long long seed = get_milliseconds();

    int* arr1 = get_random_int_array(length, -10000, 100000, seed);
    int* arr2 = get_random_int_array(length, -10000, 100000, seed);
    int* arr3 = get_random_int_array(length, -10000, 100000, seed);

    unsigned long long ta = get_milliseconds();
    sort_merge(arr1, arr1 + length);
    unsigned long long tb = get_milliseconds();

    cout << "sort_merge in " << (tb - ta) << " ms." << endl;

    ta = get_milliseconds();
    sort_merge2(arr2, arr2 + length);
    tb = get_milliseconds();

    cout << "sort_merge2 in " << (tb - ta) << " ms." << endl;

    ta = get_milliseconds();
    std::stable_sort(arr3, arr3 + length);
    tb = get_milliseconds();

    cout << "std::stable_sort in " << (tb - ta) << " ms." << endl;

    cout << std::boolalpha;

    cout << "Equal: " 
         << (std::equal(arr1, arr1 + length, arr2) &&
             std::equal(arr1, arr1 + length, arr3)) << endl;

    return 0;
}