C++ Merge Sort Implementation - Pt2 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 &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

template&lt;typename T&gt;
void Merge(T, T, T, T);
template&lt;typename T&gt;
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&lt;int&gt; a;
    for (int i = 0; i &lt; 10; i++) {
        a.push_back(10.0 * rand() / RAND_MAX);
    }
    for (int i = 0; i &lt; a.size(); i++) {
        std::cout &lt;&lt; a[i] &lt;&lt; " ";
    }
    std::cout &lt;&lt; "\n";
    // Note this swap is now in place, previously it returned a new vector
    MergeSort(a.begin(), a.end());
    for (int i = 0; i &lt; a.size(); i++) {
        std::cout &lt;&lt; a[i] &lt;&lt; " ";
    }
    std::cout &lt;&lt; "\n";
}

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

template&lt;typename T&gt;
void MergeSort(T arrBegin, T arrEnd) {
    int size = arrEnd - arrBegin;
    if (size &lt; 2) {
        return;
    }
    if (size == 2) {
        if (*arrBegin &gt; *(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:


I'm dereferencing a lot of iterators in order to swap and assign values, is there a better way to be doing this?
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) 
Also, I know nothing about templates, is there anything more to it than adding the line template&lt;typename T&gt; then line before the function and then using T within it?
I can't figure out how to get rid of std::vector&lt;int&gt; 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).
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 &lt;iterator&gt;
#include &lt;algorithm&gt;
#include &lt;utility&gt;
#include &lt;memory&gt;

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

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

template&lt;class It&gt;
void MergeSort(It begin, It end) {
    const auto size = std::distance(begin, end);
    if(size &lt; 2)
        return;
    using T = typename std::iterator_traits&lt;It&gt;::value_type;
    std::unique_ptr&lt;T[]&gt; 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:


It's better to move than copy where you can.
Your algorithm is still not stable, change if (*(i1) &lt; *(i2)) to if (!(*i2 &lt; *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.
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 &lt; and == out of all relational operators, as those are the ones used by most generic code (especially all of the standard library).
Nearly. Use an extra-level of indirection, MergeSort is the public API doing the allocating and calling the recursive MergeSortImpl which calls MergeSortMerge.