Merge sort implementation using iterators Here is my first try to implement merge sort using iterators -

#include &lt;algorithm&gt;
#include &lt;iterator&gt;
#include &lt;vector&gt;

namespace base {
namespace merge {

    template &lt;typename Iterator, typename Compare&gt;
    void mergeBack(Iterator begin, Iterator mid, Iterator end, Compare comp)
    {
        typedef typename std::iterator_traits&lt;Iterator&gt;::value_type ElemType;
        std::vector&lt;ElemType&gt; left, right;

        left.reserve(mid - begin);
        right.reserve(end - mid);

        std::copy(begin, mid, std::back_inserter(left));
        std::copy(mid, end, std::back_inserter(right));

        size_t j = 0, k = 0;
        auto i = begin;
        for (; i != end &amp;&amp; j &lt; left.size() &amp;&amp; k &lt; right.size(); ++i) {
            *i = comp(left[j], right[k]) ? left[j++] : right[k++];
        }

        while (j &lt; left.size()) {
            *(i++) = left[j++];
        }

        while (k &lt; right.size()) {
            *(i++) = right[k++];
        }
    }


    template &lt;typename Iterator, typename Compare = std::less&lt;&gt;&gt;
    void sort(Iterator begin, Iterator end, Compare comp = Compare())
    {
        if (end - begin &gt; 1) {
            const auto middle = (end - begin) / 2;
            merge::sort(begin, begin + middle, comp);
            merge::sort(begin + middle, end, comp);
            mergeBack(begin, begin + middle, end, comp);
        }
    }
}
}


I'm open to advice/suggestions about the implementation and would love to hear how I could make it better.
You should prefer to move values whenever possible.

std::move(begin, mid, std::back_inserter(left));
std::move(mid, end, std::back_inserter(right));

size_t j = 0, k = 0;
auto i = begin;

for (; i != end &amp;&amp; j &lt; left.size() &amp;&amp; k &lt; right.size(); ++i) {
    *i = std::move(comp(left[j], right[k]) ? left[j++] : right[k++]);
}

while (j &lt; left.size()) {
    *(i++) = std::move(left[j++]);
}

while (k &lt; right.size()) {
    *(i++) = std::move(right[k++]);
}


Every call of mergeBack will end up allocating 2 new buffers. You can avoid that by preallocating the secondary buffer and flip flopping between them but that is tricky to do in the recursive version. Which is why I prefer the iterative version that goes bottom up.