C++ implementation of merge sort I am studying the merge sort algorithm and implemented it. In the mergeSort function, I am allocating two new vectors. Can I do it without allocating extra memory? Are there any other suggestions?

#ifndef MERGE_SORT
#define MERGE_SORT
#include &lt;vector&gt;


template&lt;typename T&gt;
void merge(std::vector&lt;T&gt;&amp; array, std::vector&lt;T&gt; left, std::vector&lt;T&gt; right) {
    array.clear();
    auto lsize = left.size();
    auto rsize = right.size();
    unsigned int i=0, j=0;
    while (i &lt; lsize &amp;&amp; j &lt; rsize) {
        if (left[i] &lt; right[j]) {
            array.push_back(left[i]);
            ++i;
        }else {
            array.push_back(right[j]);
            ++j;
        }
    }
    for(; i&lt;lsize; ++i)
        array.push_back(left[i]);
    for(; j&lt;rsize; ++j)
        array.push_back(right[j]);
}


template&lt;typename T&gt;
void mergeSort(std::vector&lt;T&gt;&amp; seq) {
    auto n = seq.size();
    if (n &gt; 1) {
        auto start = seq.begin();
        auto end = seq.end();
        auto middle = start + n / 2;
        std::vector&lt;T&gt; left(start, middle);
        std::vector&lt;T&gt; right(middle, end);
        mergeSort(left);
        mergeSort(right);
        merge(seq, left, right);
    }
}


#endif // MERGE_SORT
Can I do it without allocating extra memory?


In fact, yes.  The trick is to merge recursively (technically, the \$O(\log N)\$ extra memory is still necessary for recursion). Here is a pseudo-code for the classic in-place merge:

// Prerequisite: [begin, mid) and [mid, end) ranges are sorted
inplace_merge(begin, mid, end)
{
    if (end - begin) &lt; 2) return;

    left = begin + (mid - begin)/2;
    right = lower_bound(mid, end, *left);

    mid = rotate(left, mid, right);

    inplace_merge(begin, left, mid);
    inplace_merge(mid, right, end);
}

Stability

The most important feature of merge sort is stability: the elements compared equal retain their original order (not very important for integers, but immensely important when sorting structured data). Your implementation loses it:

if (left[i] &lt; right[j]) {
    array.push_back(left[i]);
    ++i;
}else {
    array.push_back(right[j]);
    ++j;
}


In case of equality it is an element from right to be pushed first. Easy to fix with

if (right[j] &lt; left[i])


or

if (left[i] &lt;= right[j])


First way is preferred, because it doesn't assume existence of operator&lt;=.