C++ implementation of 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;=.