C++ Merge Sort Implementation - Pt2

Question

Following the review of my old merge sort implementation here, it appears that the biggest improvement to make was to use iterators instead of copying the vectors. Having never used iterators before, I'd like a review of the new code following that review:

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

template<typename T>
void Merge(T, T, T, T);
template<typename T>
void MergeSort(T, T);

int main()
{
    // As last time, this is just test code and does not need to be reviewed, but 
    // is included for completeness
    std::vector<int> a;
    for (int i = 0; i < 10; i++) {
        a.push_back(10.0 * rand() / RAND_MAX);
    }
    for (int i = 0; i < a.size(); i++) {
        std::cout << a[i] << " ";
    }
    std::cout << "\n";
    // Note this swap is now in place, previously it returned a new vector
    MergeSort(a.begin(), a.end());
    for (int i = 0; i < a.size(); i++) {
        std::cout << a[i] << " ";
    }
    std::cout << "\n";
}

template<typename T>
void Merge(T arr1Begin, T arr1End, T arr2Begin, T arr2End) {
    T i1 = arr1Begin;
    T i2 = arr2Begin;
    int i = 0;
    std::vector<int> res(arr2End - arr1Begin, 0);
    while (i1 < arr1End && i2 < arr2End) {
        if (*(i1) < *(i2)) {
            res[i++] = *(i1);
            std::advance(i1, 1);
        }
        else {
            res[i++] = *(i2);
            std::advance(i2, 1);
        }
    }
    while (i1 < arr1End) {
        res[i++] = *(i1);
        std::advance(i1, 1);
    }
    while (i2 < arr2End) {
        res[i++] = *(i2);
        std::advance(i2, 1);
    }
    std::copy(res.begin(), res.end(), arr1Begin);
}

template<typename T>
void MergeSort(T arrBegin, T arrEnd) {
    int size = arrEnd - arrBegin;
    if (size < 2) {
        return;
    }
    if (size == 2) {
        if (*arrBegin > *(arrEnd - 1)) {
            std::swap(*arrBegin, *(arrEnd - 1));
        }
        return;
    }
    MergeSort(arrBegin, arrBegin + size / 2);
    MergeSort(arrBegin + size / 2, arrEnd);
    return Merge(
        arrBegin, arrBegin + size / 2,
        arrBegin + size / 2, arrEnd
    );
}

My questions this time:

1. I'm dereferencing a lot of iterators in order to swap and assign values, is there a better way to be doing this?
2. Is this implementation better than my last implementation? I'm looking for answers that think about stability, efficiency in terms of speed/memory, etc. _{(Possibly an obvious question)}
3. Also, I know nothing about templates, is there anything more to it than adding the line template<typename T> then line before the function and then using T within it?
4. I can't figure out how to get rid of std::vector<int> res(arr2End - arr1Begin, 0);. Obviously this goes against the templating, how should I store the results while I'm doing the merge? (Edit: since looking back at the previous accepted answer, I figure I should create a new vector outside the original call to MergeSort (inside main) and pass the .begin() of that array as the destination, rather than defining a new array inside each Merge() call and using std::copy. Is this correct?)

Edit: Thanks to @ratchetfreak for pointing out a bug whereby I was overwriting elements of arr1 without storing the overwritten element elsewhere beforehand (essentially losing it).

Answer 1

Overview

Its an improvement over the first version, but still some work to go. I think most of my comments below are relatively minor and the worst ones come from assuming the type being sorted is an int.

The other major flaw is still efficiency (though it has improved considerably). First prefer move to copy. But you also allocate a res vector on each recursive call down MergeSortMerge(). That can be made more efficient by only doing it once at the top level:

mergeSort(begin, end)
     Allocate temp array here
     mergeSortDo(begin, end, tBegin);  // you can 

mergeSortDo(beg, end, tBeg)
     Your Merge in here just pass sections of the temp forward.
     mergeSortDo(beg, mid, tBeg);
     mergeSortDo(mid, end, tMid);
     mergeSortMerge(begin, mid, end, tBeg)

mergeSortMerge(beg, mid, end, tBeg)
     Your MergeSortMereHere (with already allocated space.

Code Review

Please specify parameters.

Please provide parameter names even in declarations. It helps understanding what your code does and is part of the "Self Documenting Code" principle.

template<typename T>
void Merge(T, T, T, T);
template<typename T>
void MergeSort(T, T);

Range Based For

If you are looping over a whole container use the range based for:

    for (int i = 0; i < a.size(); i++) {
        std::cout << a[i] << " ";
    }

    // This is easier to write:
    for (auto const& value: a) {
        std::cout << value << " ";
    }

Not all iterators are Random Accesses

There are several categories of iterators.

• Input
• Forward: (Is a Input with a few more properties)
• BiDirectional: (Is a Forward with a few more properties)
• RandomAccess: (Is a BiDirectional with a few more properties)
• Contiguous: (Is a RandomAccess with a few more properties)

Now you should be able to perform a sort on any iterator that is a BiDirectional iterator. But BiDirectional iterators don't support all the features of RandomAccess iterator.

The trouble is here:

    int size = arrEnd - arrBegin;

Subtracting two iterators requires that they are at least Random Access iterators. But the standard comes to your help here:

    int size = std::distance(arrBegin, arrEnd);

This returns the distance between two iterators (from the same sequence).

Standard Swap usage

For this to work:

    std::swap(*arrBegin, *(arrEnd - 1));

The two object need to be a type that the standard understands. So currently you can only swap types that are in the namespace std. std::swap will fallback to using a temporary and assignment but this is not always as efficient as possible and lots of types define their own swap to make it much more efficient (but that will not happen here). What you want to do is:

    using std::swap;
    swap(*arrBegin, *(arrEnd - 1));

This says bring std::swap into the current scope so we can use it automatically as a backup. Now when you call swap() it does Koenig lookup (or ADL). This means it checks the types of the arguments and sees what namespace they are in; it then looks for a swap() function in that namespace (because if you define a type in a namespace you also define the swap function in the same namespace). If it finds this type specific swap() it will use that but if it does not find it then it will fallback to using swap() in the current context (in this case std::swap()).

There is a shortcut for the above.

 std::iter_swap(arrBegin, arrEnd - 1);

Do you really want a return here?

    return Merge(
        arrBegin, arrBegin + size / 2,
        arrBegin + size / 2, arrEnd
    );

Don't assume iterators point integer containers.

Here you assume the type is int. Iterators can point at any type. The other thing you assume is that the value can be constructed with a defautl value (not true of all types).

    std::vector<int> res(arr2End - arr1Begin, 0);

The type the iterator points too is: std::iterator_traits<T>::value_type.

In this better to create an empty array and reserve the size you want (so it does not need to realloc a bigger chunk of memory)

    using ValueType = std::iterator_traits<T>::value_type;
    std::vector<ValueType> res;
    res.reserve(arr2End - arr1Begin);  // You will now need to use `emplace_back()`

Stable Sort

A very nice property of a sort is when it is stable (its a maths term go look it up).

Change this line:

        if (*(i1) < *(i2)) {

        // Into
        if (*(i1) <= *(i2)) {
        // Basically if the items are equal you will choose from the
        // left sub container rather than right. This way values that
        // are equal retain their relative order to each other.

Prefer move to copy.

This performs a copy.

            res[i++] = *(i1);

When the type is not an integer (say you are sorting strings). This is not a very efficient way to do it. In C++11 we introduced move semantics which allows an object to be moved (in the case of a string that means moving its pointers and not the string). As you can imagine this makes it much more efficient than a copy.

            res[i++] = std::move(*i1);
            // If you have updated your array as above then you would use.
            res.emplace_back(std::move(*i1));

Prefer Algorithms to loops.

    while (i1 < arr1End) {
        res[i++] = *(i1);
        std::advance(i1, 1);
    }

This is basically a copy from one container to another. There is an algorithm for that.

   i1 = std::copy(i1, arr1End, &res[i]);

But we don't want to copy all the memebers. We want to move them. And there is an algorithm for that:

   i1 = std::move(i1, arr1End, &res[i]);

I think I mentioned we want to move rather than copy.

     std::copy(res.begin(), res.end(), arr1Begin);

Answer 2

Well, the first point is that you are still allocating memory for every single merge. That's expensive.

Second, you are always copying all elements. That's inefficient too.

Third, prefer to move instead of copying. Some types are move-only, others just far more efficiently moved.

Try something along these lines:

#include <iterator>
#include <algorithm>
#include <utility>
#include <memory>

template<class It>
void MergeSortMerge(It begin, It mid,
    typename std::iterator_traits<It>::value_type* aux)
{
    while(begin != mid && !(*mid < *begin))
        ++begin;
    if(begin != mid)
        std::move(begin, mid, aux);
    for(; begin != mid; ++begin) {
        if(*mid < *aux) {
            *begin = std::move(*mid);
            ++mid;
        } else {
            *begin = std::move(*aux);
            ++aux;
        }
    }
}

template<class It>
void MergeSortImpl(It begin, It end,
    typename std::iterator_traits<It>::value_type* aux)
{
    const auto size = std::distance(begin, end);
    if(size < 2)
        return;
    const auto mid = std::next(begin, size / 2);
    MergeSortImpl(begin, mid, aux);
    MergeSortImpl(mid, end, aux);
    MergeSortMerge(begin, mid, aux);
}

template<class It>
void MergeSort(It begin, It end) {
    const auto size = std::distance(begin, end);
    if(size < 2)
        return;
    using T = typename std::iterator_traits<It>::value_type;
    std::unique_ptr<T[]> aux = new T[size / 2];
    MergeSortImpl(begin, end, aux.get());
}

The one style-comment I have is that streaming a single character as a char is marginally more efficient than as a length-1-string.

You only use arrEnd - 1 in two places, where you could use arrBegin + 1 instead. Changing that allows the use of mutable forward-iterators, whereas before you required mutable bidirectional iterators.

Adressing your extra questions:

1. It's better to move than copy where you can.
2. Your algorithm is still not stable, change if (*(i1) < *(i2)) to if (!(*i2 < *i1)).
   You have fewer allocations than before, one for every merge instead of one for every recursive call to sort. That's still far more than the single one needed though.

3. That's the beginning. Next, you have to really think about how to most generically use the type / expressions affected, and to minimize the interface used.

   std::iterator_traits, std::distance and std::advance are your friend there, and it wouldn't be amiss to only use < and == out of all relational operators, as those are the ones used by most generic code (especially all of the standard library).

4. Nearly. Use an extra-level of indirection, MergeSort is the public API doing the allocating and calling the recursive MergeSortImpl which calls MergeSortMerge.

Answer 3

I would make it clearer that you are looking at a single array that is split in the middle in the parameters.

Instead of pre-filling the result vector you can reserve it and push back the values. The value type of the iterator can be discovered by using std::iterator_traits<T>::value_type. The reserve is not strictly necessary but it will avoid reallocations that aren't needed.

template<typename T>
void Merge(T begin, T mid, T end) {
    T arr1Begin = begin;
    T arr1End = mid;
    T arr2Begin = mid;
    T arr2End = end;

    T i1 = arr1Begin;
    T i2 = arr2Begin;
    int i = 0;
    std::vector<std::iterator_traits<T>::value_type> res;
    res.reserve(arr2End - arr1Begin);
    while (i1 < arr1End && i2 < arr2End) {
        if (*(i1) < *(i2)) {
            res.push_back(*(i1));
            std::advance(i1, 1);
        }
        else {
            rres.push_back(*(i2));
            std::advance(i2, 1);
        }
    }
    std::copy(i1 , arr1End, arr1Begin+res.size());

    std::copy(res.begin(), res.end(), arr1Begin);
}

The final while loops can be replaced by either leaving the rest of i2 in place or copying the rest of i1 to the end of the array.

A further improvement would be to use moves instead of copies.