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 this template<typename I> // Notice the template void merge_sort(I begin, I end) // Just means I don't care what type {} // of iterator is used.
Same applies to merge().
Rather than creating sub arrays in merge_sort() I would do it inside merge(). With your current implementation you have a space complexity of \$O(N^2)\$. If you do it inside the merge 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 of merge() 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 use if () {} else {} I prefer to use the Condition 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 use std::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"; }
