Merge sort algorithm implementation using C++ I'm trying to learn proper C++ and algorithms at the same time. 

I particularly feel weird about my iterators usage in merge function. Is this a good way to handle it? I've modeled the signature after the STL std::merge method in &lt;algorithm&gt;.

I've tagged it as C++11 as well, because ideally I would've liked to make use of the new features like move semantics and rvalues, but it seems that I'm misunderstanding how they're supposed to work - no matter where I try to use them, my running time actually drops...

#include &lt;vector&gt;

typedef std::vector&lt;int&gt;::iterator vec_it;
void merge(vec_it left, vec_it left_end, vec_it right, vec_it right_end, vec_it numbers)
{
    while (left != left_end) {
        if (*left &lt; *right || right == right_end) {
            *numbers = *left;
            ++left;
        } else {
            *numbers = *right;
            ++right;
        }

        ++numbers;
    }

    while (right != right_end) {
        *numbers = *right;
        ++right;
        ++numbers;
    }
}

void merge_sort(std::vector&lt;int&gt;&amp; numbers)
{
    if (numbers.size() &lt;= 1) {
        return;
    }

    std::vector&lt;int&gt;::size_type middle = numbers.size() / 2;
    std::vector&lt;int&gt; left(numbers.begin(), numbers.begin() + middle);
    std::vector&lt;int&gt; right(numbers.begin() + middle, numbers.end());

    merge_sort(left);
    merge_sort(right);

    merge(left.begin(), left.end(), right.begin(), right.end(), numbers.begin());
}
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&lt;int&gt;&amp; numbers)
{}

// My version looks like this

template&lt;typename I&gt;                 // 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&lt;int&gt;::size_type middle = numbers.size() / 2;
std::vector&lt;int&gt; left(numbers.begin(), numbers.begin() + middle);
std::vector&lt;int&gt; 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 &lt; midPoint &amp;&amp; r &lt; end)
{
    if (*l &lt; *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 &lt; midPoint)
{   *i  = *l;
    ++i;
    ++l;
}
while(r &lt; 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 ? &lt;TrueWork&gt; : &lt;FalseWork&gt;. 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 &lt; midPoint &amp;&amp; r &lt; end)
{
    *i = std::move((*l &lt; *r) ? *l++ : *r++);
    ++i;
}
while(l &lt; midPoint)
{   *i  = std::move(*l++);
    ++i;
}
while(r &lt; 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 &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;algorithm&gt;
#include &lt;iterator&gt;

template&lt;typename I&gt;
void doMerge(I begin, I midPoint, I end)
{
    typename std::vector&lt;typename std::iterator_traits&lt;I&gt;::value_type&gt; 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 &lt; midAlt &amp;&amp; r &lt; endAlt)
    {
        *i = std::move((*l &lt; *r) ? *l++ : *r++);
        ++i;
    }
    while(l &lt; midAlt)
    {   *i  = std::move(*l++);
        ++i;
    }
    while(r &lt; endAlt)
    {   *i  = std::move(*r++);
        ++i;
    }
}
template&lt;typename I&gt;
void mergeSort(I begin, I end)
{
    std::size_t length  = std::distance(begin, end);
    if (length &lt;= 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&lt;int&gt;    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&lt;int&gt;(std::cout, ", "));
    std::cout &lt;&lt; "\n";
}