Merge sort C++14 implementation

Question

Here is my merge sort c++ implementation. Looking for code improvement and optimization opinion. Just one question which is better *k++ = *i++; or, *k = *i; ++k; ++i;.

/*
 *    Merge Sort
 */

#include <iostream>
#include <vector>

void mergeSort(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator r);
void merge(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator q, std::vector<int>::iterator r);
void print(const std::vector<int> &v);

int main()
{
    std::ios_base::sync_with_stdio(false);

    std::vector<int> v;

    int temp = 0;
    while (std::cin >> temp) {
        v.push_back(temp);
    }

    // Sort
    mergeSort(v, v.begin(), v.end() - 1);
    // Print the vector after sorting.
    print(v);

    return 0;
}

void mergeSort(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator r) {
    // Base case: if (p >= r) then return
    if (p < r) {
        auto q = p + (r - p) / 2;

        mergeSort(v, p, q);
        mergeSort(v, q+1, r);
        merge(v, p, q, r);
    }
}

void merge(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator q, std::vector<int>::iterator r) {
    std::vector<int>::size_type leftVectorSize = q - p + 1;
    std::vector<int>::size_type rightVectorSize = r - q;

    std::vector<int> vLeft(leftVectorSize);
    std::vector<int> vRight(rightVectorSize);

    // Copy elements p to q
    auto it = p;
    for (auto &i : vLeft) {
        i = *it++;
    }

    // Copy elements q + 1 to r
    for (auto &i : vRight) {
        i = *it++;
    }

    auto i = vLeft.cbegin(), j = vRight.cbegin();
    auto k = p;

    // Compare and merge
    while (i != vLeft.end() && j != vRight.end()) {
        if (*i <= *j) {
            *k++ = *i++;
        } else {
            *k++ = *j++;
        }
    }

    // Copy rest of the elements if any
    while (i != vLeft.end()) {
        *k++ = *i++;
    }

    // Copy rest of the elements if any
    while (j != vRight.end()) {
        *k++ = *j++;
    }
}

void print(const std::vector<int> &v) {
    for (const auto &i : v) {
        std::cout << i << "\n";
    }
}

Answer 1

Advice 1

mergeSort(v, v.begin(), v.end() - 1);

So your implementation requires the actual vector + two iterators; this is an anti-pattern, you should strive for the following API:

mergeSort(v.begin(), v.end());

Note v.end() instead of v.end() - 1, since end() points to the one element past the last element; this is the STL approach.

Advice 2

Same applies to the merge.

Summa summarum

If you want to improve your coding, you could start by investigating the following:

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

void mergeSort(std::vector<int>::iterator begin,
               std::vector<int>::iterator end);

void merge(std::vector<int>::iterator begin,
           std::vector<int>::iterator middle,
           std::vector<int>::iterator end);

void print(const std::vector<int> &v);

int main()
{
    std::ios_base::sync_with_stdio(false);
    
    std::vector<int> v;
    
    int temp = 0;
    while (std::cin >> temp) {
        v.push_back(temp);
    }
    
    // Sort
    mergeSort(v.begin(), v.end());
    // Print the vector after sorting.
    print(v);
    
    return 0;
}

void mergeSort(std::vector<int>::iterator begin, std::vector<int>::iterator end) {
    auto distance = std::distance(begin, end);
    
    if (distance < 2) {
        return;
    }
    
    auto middle = begin;
    std::advance(middle, distance / 2);
    mergeSort(begin, middle);
    mergeSort(middle, end);
    merge(begin, middle, end);
}

void merge(std::vector<int>::iterator begin,
           std::vector<int>::iterator middle,
           std::vector<int>::iterator end) {
    auto distance = std::distance(begin, end);
    std::vector<int> aux(distance);
    
    auto left = begin;
    auto left_bound = middle;
    auto right = middle;
    auto right_bound = end;
    size_t aux_index = 0;
    
    while (left != left_bound && right != right_bound) {
        if (*right < *left) {
            aux[aux_index++] = *right;
            ++right;
        } else {
            aux[aux_index++] = *left;
            ++left;
        }
    }
    
    std::copy(left, left_bound, &aux[aux_index]);
    std::copy(right, right_bound, &aux[aux_index]);
    std::copy(aux.begin(), aux.end(), begin);
}

void print(const std::vector<int> &v) {
    for (const auto &i : v) {
        std::cout << i << " ";
    }
    
    std::cout << std::endl;
}

Advice 3

Making the sort more idiomatic (a template) and efficient (double buffer strategy) is not too hard:

template<typename RandomIter1, typename RandomIter2>
void merge(RandomIter1 begin,
           RandomIter1 middle,
           RandomIter1 end,
           RandomIter2 aux) {
    RandomIter1 left = begin;
    RandomIter1 right = middle;
    RandomIter1 left_bound = middle;
    RandomIter1 right_bound = end;
    
    while (left != left_bound and right != right_bound) {
        if (*right < *left) {
            *aux = *right;
            ++right;
        } else {
            *aux = *left;
            ++left;
        }
        
        ++aux;
    }
    
    std::copy(left, left_bound, aux);
    std::copy(right, right_bound, aux);
}

template<typename RandomIter1, typename RandomIter2>
void merge_sort(RandomIter1 source_begin,
                RandomIter1 source_end,
                RandomIter2 target_begin,
                RandomIter2 target_end) {
    auto distance = std::distance(source_begin, source_end);
    
    if (distance < 2) {
        return;
    }
    
    RandomIter1 source_middle = source_begin;
    RandomIter2 target_middle = target_begin;
    std::advance(source_middle, distance >> 1); // distance >> 1 is the same as
                                         // distance / 2
    std::advance(target_middle, distance >> 1);
    
    merge_sort(target_begin,
               target_middle,
               source_begin,
               source_middle);
    
    merge_sort(target_middle,
               target_end,
               source_middle,
               source_end);
    
    merge(source_begin,
          source_middle,
          source_end,
          target_begin);
}

template<typename RandomIter>
void merge_sort(RandomIter begin, RandomIter end) {
    auto distance = std::distance(begin, end);
    
    if (distance < 2) {
        return;
    }
    
    using value_type = typename std::iterator_traits<RandomIter>::value_type;
    value_type* aux = new value_type[distance];
    std::copy(begin, end, aux);
    merge_sort(aux, aux + distance, begin, end);
    delete[] aux;
}

When I compare the above to your version (demo here), I get the following figures when using -O3 optimization flag:

OP time: 377 milliseconds.
coderodde time: 144 milliseconds.
Algorithms agree: true

Hope that helps.

PS

Continuing on double buffer strategy, I have to add that when merging, we merge the two sorted runs in the source array to the target array. No need to add left + right vector all over again. The rest is source/target array orchestration such that the sorted result array ends up in the input array.

Answer 2

This code is old, and using an older standard, but since it came up in 2024, we might as well take a swing at modernizing it. I won’t be discussing the implementation… just the interface. I’ll leave modernizing the implementation as an “exercise for the reader”.

So this is the interface in the original post:

void mergeSort(std::vector<int> &v, std::vector<int>::iterator p, std::vector<int>::iterator r);

(I’m assuming merge() is just an implementation detail.)

The accepted answer has already pointed out that this interface is… not great. The proposed improved interface was:

template<typename RandomIter>
void merge_sort(RandomIter begin, RandomIter end);

This is much better… but still not great. Even back in ancient C++ times, it still would have been better to provide a range-based overload. We had std::begin() and std::end() since C++11, and while std::ranges::subrange did not exist, it was trivial to make something much like it (I know this because I did, several times).

So even back in C++11 times, a truly great interface would have been:

template<typename ReversibleContainer>
void merge_sort(ReversibleContainer&);

Note that ReversibleContainer was only bidirectional, not random-access, but we don’t need random-access for a merge sort anyway. There was no standard named requirement that quite suited our needs back then, so we might have had to roll our own BidirectionalContainer or RandomAccessView something like that. Not that it really matters, because no one was doing any formal checking of that kind of stuff back then.

Anywho, back then it was “the norm” to make an iterator-pair interface canonical, and have the “range” interface defer to it:

template<typename BidirectionalIterator>
void merge_sort(BidirectionalIterator, BidirectionalIterator)
{
    // ...
}

template<typename BidirectionalRange>
void merge_sort(BidirectionalRange& r)
{
    using std::begin;
    using std::end;

    return merge_sort(begin(r), end(r));
}

This takes me back, because I wrote a LOT of code like this back in the day. I even wrote tutorials teaching that this was the way to do it. (That blog is long since gone, but I was pleasantly surprised to discover it’s still available via the Wayback Machine. I’ll definitely be doing an updated version sometime in the not-too-distant future.)

These days, things have changed. With the addition of the standard ranges library, it now makes more sense to make the range version canonical, and have the iterator version defer to it:

template<typename BidirectionalRange>
void merge_sort(BidirectionalRange&)
{
    // ...
}

template<typename BidirectionalIterator>
void merge_sort(BidirectionalIterator first, BidirectionalIterator last)
{
    return merge_sort(std::ranges::subrange{first, last});
}

Why? Because the range always has at least as much as information as the iterator pair, and potentially more. For a concrete example of what I’m talking about, consider that, at some point, the merge sort algorithm has to get the size of the input sequence. That means:

std::ranges::distance(r);           // for the range
std::ranges::distance(first, last); // for the iterator pair

For most ranges, there is no difference. For std::vector, for example, distance(vector) and distance(begin(vector), end(vector)) are essentially identical.

But… consider std::list.

std::list’s iterators are bidirectional. That means that when you do distance(begin(list), end(list)), the function has to iterate through every one of the iterators in the list, jumping all over the place in memory, counting the steps. But std::list knows its size! So when you do distance(list), it’s a trivial load of a single integer value. It’s basically free.

There will never be a case where distance(begin(r), end(r)) is more efficient than distance(r), for the simple reason that if that were the case, the range could just do the begin(*this) and end(*this) internally. distance(r) will always be at least as efficient as distance(begin(r), end(r)), if not more so. And the same logic holds true for other functions, not just distance().

This is the lesson. In modern C++, ranges are the way. Always prefer to work with ranges primarily, and only use iterators as a last resort when a range really doesn’t make sense.

There’s one more thing that the range library changed. Back in the day, a range’s begin() and end() always returned the same type. Nowadays, that is no longer the case. Instead of a begin/end iterator pair, we talk about iterator/sentinel pairs. So while “classic” algorithms looks like f(iterator, iterator), modern algorithms look more like f(iterator, sentinel).

That means our interface should be:

template<typename BidirectionalRange>
void merge_sort(BidirectionalRange&)
{
    // ...
}

template<typename BidirectionalIterator, typename Sentinel>
void merge_sort(BidirectionalIterator first, Sentinel last)
{
    return merge_sort(std::ranges::subrange{first, last});
}

And of course, there is no reason not to take a universal reference to the range, so:

template<typename BidirectionalRange>
void merge_sort(BidirectionalRange&&)
{
    // ...
}

template<typename BidirectionalIterator, typename Sentinel>
constexpr void merge_sort(BidirectionalIterator first, Sentinel last)
{
    return merge_sort(std::ranges::subrange{first, last});
}

(You might be scratching your head wondering why you would ever want to sort a rvalue range. Rvalue basically means “about to be destroyed”… what is the sense of spending all that effort sorting a sequence that is about to be destroyed? You’re right, that would be silly… but quite often we are dealing not with sequences directly, but rather with views of sequences. It is not uncommon at all to be passed a temporary view of a sequence, which you could then sort, then the view immediately dies, but the (now sorted) sequence lives on. And, in fact, if we didn’t support taking rvalues, then we wouldn’t be able to take temporary views, which could be quite frustrating.)

And of course, we should constexpr all the things:

template<typename BidirectionalRange>
constexpr void merge_sort(BidirectionalRange&&)
{
    // ...
}

template<typename BidirectionalIterator, typename Sentinel>
constexpr void merge_sort(BidirectionalIterator first, Sentinel last)
{
    return merge_sort(std::ranges::subrange{first, last});
}

I would also use automatic return type deduction, just in case we ever decide to return something other than void:

template<typename BidirectionalRange>
constexpr auto merge_sort(BidirectionalRange&&)
{
    // ...
}

template<typename BidirectionalIterator, typename Sentinel>
constexpr auto merge_sort(BidirectionalIterator first, Sentinel last)
{
    return merge_sort(std::ranges::subrange{first, last});
}

That about takes us up to C++17 (std::ranges::subrange not withstanding). Now it’s time to go full C++20 and beyond.

The biggest and most important step to take when moving to C++20 is to constrain your templates. Since we put the old-fashioned named requirements in the template preamble, we’re already half-way there. We just need to replace the old-school names with concepts:

template<std::ranges::bidirectional_range R>
constexpr auto merge_sort(R&&)
{
    // ...
}

template<std::bidirectional_iterator I, std::sentinel_for<I> S>
constexpr auto merge_sort(I first, S last)
{
    return merge_sort(std::ranges::subrange{first, last});
}

But we require more than just that the range/iterator is bidirectional. To sort the range, we need to be able to do a lot more, like compare the elements, swap them, etc.. That’s quite a few requirements to test for, but happily, the standard library already comes with a concept that handles all that: std::sortable.

template<std::ranges::bidirectional_range R>
requires std::sortable<std::ranges::iterator_t<R>>
constexpr auto merge_sort(R&&)
{
    // ...
}

template<std::bidirectional_iterator I, std::sentinel_for<I> S>
requires std::sortable<I>
constexpr auto merge_sort(I first, S last)
{
    return merge_sort(std::ranges::subrange{first, last});
}

We’re almost done. One feature we’re missing that has existed since ancient times is the ability to change the behaviour of algorithms. For example, even old-fashioned std::sort() has always allowed you to specify a custom comparator, rather than use operator<.

Modern algorithms take that to the next level. Not only do they define default operations in terms of function objects and allow you to replace those function objects, they also allow you to do projections.

For example, say you have a book class with title and author string members, and you want to sort by author in descending order. As far back as C++98, you were able to do this:

struct compare
{
    bool operator()(book const& a, book const& b) const
    {
        return b.author < a.author;
    }
};

std::sort(books.begin(), books.end(), /* most vexing parse */ (compare()));

With lambdas that simplifies enormously to:

std::sort(begin(books), end(books), [](auto&& a, auto&& b) { return b.author < a.author; })

But with projections, you can much more clearly express the intent to sort in descending order by author:

std::ranges::sort(books, std::ranges::greater{}, &book::author);

Adding this functionality is not difficult, and is basically identical for every algorithm you write:

1. Add the defaulted template parameters for the comparator and projector. Comparators always default to std::ranges::less. Projectors always default to std::identity.
2. Add the function parameters for the comparator and projector. They both default to {}.
3. Make all your constraints work with the projected types and values, and comparator calls and results. Standard concepts like std::sortable come with that support already built in, but if you need to do it manually, it’s mostly just a matter of replacing Iterator with std::projected<Iterator, Proj>.
4. Finally pass the comparator and projector along whenever required in the function body:

template<
    std::ranges::bidirectional_range R,
    typename Comp = std::ranges::less,
    typename Proj = std::identity
>
requires std::sortable<std::ranges::iterator_t<R>, Comp, Proj>
constexpr auto merge_sort(R&&, Comp comp = {}, Proj proj = {})
{
    // ...
}

template<
    std::bidirectional_iterator I,
    std::sentinel_for<I> S,
    typename Comp = std::ranges::less,
    typename Proj = std::identity
>
requires std::sortable<I, Comp, Proj>
constexpr auto merge_sort(I first, S last, Comp comp = {}, Proj proj = {})
{
    return merge_sort(std::ranges::subrange{first, last}, comp, proj);
}

And that’s it. All you need to do is fill in the // ... with an actual implementation.

There are a few complications, though:

1. If you’re going to call non-constexpr functions (like std::inplace_merge(), which won’t be constexpr until C++26), then you might have to drop the constexprs… at least temporarily.
2. If you’re going to call the function recursively, then you can’t deduce the return type, so you’ll probably have to add an explicit -> void.

The hard part of merge sort is the merging, of course. But the same ideas we used to develop a modern interface for our merge_sort() function could be applied to making a merge() or inplace_merge(). Or you could just peek at the standard library versions and see what their interfaces look like.

Happy coding!

Answer 3

As indi mentions, C++20 features allow the code to be greatly simplified. See the example below.

template<
    std::ranges::bidirectional_range R,
    typename Comp = std::ranges::less,
    typename Proj = std::identity
>
requires std::sortable<std::ranges::iterator_t<R>, Comp, Proj>
constexpr auto merge_sort(R&& r, Comp comp = {}, Proj proj = {}) {
    if (std::ranges::distance(r) < 2)
        return;
    
    auto mid = std::ranges::next(std::ranges::begin(r), std::ranges::distance(r) / 2);

    merge_sort(std::ranges::subrange{std::ranges::begin(r), mid}, comp, proj);
    merge_sort(std::ranges::subrange{mid, std::ranges::end(r)}, comp, proj);

    std::ranges::inplace_merge(std::ranges::begin(r), mid, std::ranges::end(r), comp, proj);
}

template<
    std::bidirectional_iterator I,
    std::sentinel_for<I> S,
    typename Comp = std::ranges::less,
    typename Proj = std::identity
>
requires std::sortable<I, Comp, Proj>
constexpr auto merge_sort(I first, S last, Comp comp = {}, Proj proj = {}) {
    return merge_sort(std::ranges::subrange{first, last}, comp, proj);
}