Looks good.

Couple of things I would do differently (not that your way is wrong).

Rather than pass references to the containers around I would pass iterators into the containers. This allows your sort algorithm to be container agnostic:

void merge_sort(std::vector<int>& numbers){}// My version looks like thistemplate<typename I>                 // Notice the templatevoid merge_sort(I begin, I end)      // Just means I don't care what type{}                                   // of iterator is used.

Same applies tomerge().

Rather than creating sub arrays inmerge_sort() I would do it insidemerge(). With your current implementation you have a space complexity of \$O(N^2)\$. If you do it inside themerge you just need to allocate enough space to merge the current two ranges which is at most \$O(2N)\$ => \$O(N)\$.

Where you have:

std::vector<int>::size_type middle = numbers.size() / 2;std::vector<int> left(numbers.begin(), numbers.begin() + middle);std::vector<int> right(numbers.begin() + middle, numbers.end());merge_sort(left);merge_sort(right);// My version looks like this:std::size_t mid      = length/2;I           midPoint = std::next(begin, mid);// Merge in place.mergeSort(begin, midPoint);mergeSort(midPoint, end);

I could not work out how to merge without using a temporary (and I don;t have my copy of Knuth here). So my version ofmerge() merges the two sorted sub vectors into a temporary then copies back over the original.

Looking at your merge code it's slightly hard to follow (but I groked it). I personally prefer a simpler version.

// In this loop://    l:     current position in left  sub-array//    r:     current position in right sub-array//    i:     current position into merged array.//    Note because we are merging in-place.//    begin/midPoint/end are iterators to the input arrays that//    split it into two parts.while(l < midPoint && r < end){    if (*l < *r)    {    *i = *l;         ++i;         ++l;    }    else    {    *i = *r;         ++i;         ++r;    }}// One of the ranges is empty at this point.// So only one of the loops will execute.while(l < midPoint){   *i  = *l;    ++i;    ++l;}while(r < end){   *i  = *r;    ++i;    ++r;}

A slight variation on this that I use; Where you useif () {} else {} I prefer to use theCondition Operator =>Test ? <TrueWork> : <FalseWork>. I also have done this a few times and can safely compress++ operations onto the same lines (Note I don't compress all of them; this is just personal preferences as I think it makes it easier to read this way). Which leaves me with:

while(l < midPoint && r < end){    *i = std::move((*l < *r) ? *l++ : *r++);    ++i;}while(l < midPoint){   *i  = std::move(*l++);    ++i;}while(r < end){   *i  = std::move(*r++);    ++i;}

Notice: I usestd::move() here. This is because my sort works on generic containers (not just integer containers). So I may be sorting an array of strings.

Final result is:

#include <vector>#include <iostream>#include <algorithm>#include <iterator>template<typename I>void doMerge(I begin, I midPoint, I end){    typename std::vector<typename std::iterator_traits<I>::value_type> TmpVec;    TmpVec  tmp(std::make_move_iterator(begin), std::make_move_iterator(end));    TmpVec::iterator   beginAlt   = std::begin(tmp);    TmpVec::iterator   endAlt     = std::end(tmp);    TmpVec::iterator   midAlt     = std::next(beginAlt, std::distance(begin, midPoint));    TmpVec::iterator   l   = beginAlt    TmpVec::iterator   r   = midAlt;    I                  i   = begin;    while(l < midAlt && r < endAlt)    {        *i = std::move((*l < *r) ? *l++ : *r++);        ++i;    }    while(l < midAlt)    {   *i  = std::move(*l++);        ++i;    }    while(r < endAlt)    {   *i  = std::move(*r++);        ++i;    }}template<typename I>void mergeSort(I begin, I end){    std::size_t length  = std::distance(begin, end);    if (length <= 1)    {   return;    }    std::size_t mid      = length/2;    I           midPoint = std::next(begin, mid);    mergeSort(begin, midPoint);    mergeSort(midPoint, end);    doMerge(begin, midPoint, end);}int main(){    std::vector<int>    data  {{ 5,12,45,2,67,8}};    mergeSort(std::begin(data), std::end(data));    std::copy(std::begin(data), std::end(data), std::ostream_iterator<int>(std::cout, ", "));    std::cout << "\n";}

• \$\begingroup\$tmp(std::distance(begin, end)) will value-initialize. OP suggestedin the updated question to copy totmp in the ctor and then merging back tobegin. What do you think?\$\endgroup\$

  dyp

  – dyp

  2014-05-14 23:04:10 +00:00

  CommentedMay 14, 2014 at 23:04
• \$\begingroup\$@dyp: Good idea. Altered final example. Took a few tweaks to make sure we always use move semantics.\$\endgroup\$

  Loki Astari

  – Loki Astari

  2014-05-14 23:47:51 +00:00

  CommentedMay 14, 2014 at 23:47

I could not work out how to merge without using a temporary

There are two distinct flavours ofmerge. One is a generic merge of two totally unrelated ranges, which cannot possibly happen inplace, with the signature

template <typename I>void merge(I first1, I last1, I first2, I last2, I target);

The second one, actually employed in the merge sort, assumes that the range are adjacent, hence less parameters:

template <typename I>void merge(I first, I mid, I last);

This one can be done inplace, while maintaining stability. The algorithm is so beautiful, I can't help but spell it out here. It is also very instructive. Notice the recursive nature of the merge phase; that's what makes inplace possible.

// Preconditions: is_sorted(first, mid) && is_sorted(mid, last)template <typename I>void merge(I first, I mid, I last){    if (first == mid || mid == last) return;    I lm = midpoint(first, mid);    I rm = lower_bound(mid, last, *lm);    mid = rotate(lm, mid, rm);    merge(l, lm, mid);    merge(mid, rm, last);}

midpoint is very straightforward;lower_bound is a variation on a binary search theme.rotate is the most saddle for you have to understand what does it return, and why. Of course there's huge room for optimization.

There is a suspicious piece in yourmerge function:

    if (*left < *right || right == right_end) ....

You're testing the value at theright iteratorbefore testing if the iterator is valid! Should be:

    if (right == right_end || *left < *right) ....

Additionally you compare items to be merged with a 'less-than' instead of 'less-or-equal' operator. That causes takingequal items from theright part first, which violates the usual stability of the merge-sort.

The whole merge routine more compact:

{    while (left != left_end && right != right_end) {        if (*left <= *right) {            *numbers ++ = *left ++;        } else {            *numbers ++ = *right ++;        }    }    while (left != left_end)        *numbers ++ = *left ++;    while (right != right_end)        *numbers ++ = *right ++;}

• c++
• algorithm
• c++11
• sorting
• mergesort