Mergesort with std::vector I made a mergesort implementation based on this code. Please review my C++ version.

using size = std::size_t;

template&lt;typename T&gt;
void merge(std::vector&lt;T&gt;&amp; v, size low, size mid, size high) {
    size i = low, j = mid+1;
    std::vector&lt;T&gt; old{v};
    for (size x = low; x &lt;= high; ++x) {
        if (i &gt; mid) {
            v[x] = old[j++];
        } else if (j &gt; high){
            v[x] = old[i++];
        } else if (old[j] &lt; old[i]) {
            v[x] = old[j++];
        } else {
            v[x] = old[i++];
        }
    }
}

template&lt;typename T&gt;
void sort(std::vector&lt;T&gt;&amp; v, size low, size high) {
    if (high &lt;= low) {
        return;
    }
    size mid = (high+low)/2;
    sort(v,0,mid);
    sort(v,mid+1,high);
    merge(v,low,mid,high);
}

template&lt;typename T&gt;
void sort(std::vector&lt;T&gt;&amp; v) {
    if (v.size() &lt; 2) {
        throw std::out_of_range("out of range");
    }
    sort(v,0,v.size()-1);
}
You have decided your ranges are inclusive:

sort(v,0,v.size()-1);


So low=>lowest member, high=>highest member.
Most C++ code uses the one past the end system (see iterators). Not a huge deal. It just means you need to use operator&lt;= rather than operator&lt; and you have to sprinkle a couple of +1 around.

Your main merge loop is easier to write if you concentrate on what it is supposed to do (Compare items from the two ranges).

while(i &lt;= mid &amp;&amp; j &lt;= high) {
    if (old[j] &lt; old[i]) {
        v[x++] = old[j++];
    } else {
        v[x++] = old[i++];
    }
}


At this point one of the ranges is exhausted, so all the elements must come from the other range. So just copy them.

while(i &lt;= mid) {
   v[x++] = old[i++];
}
while(j &lt;= high) {
   v[x++] = old[j++];
}


But we can also replace manual loops using algorithms:

std::copy(&amp;old[i], &amp;old[mid+1],  &amp;v[x]); x+= (mid-i)+1;
std::copy(&amp;old[j], &amp;old[high+1], &amp;v[x]);


Also, you are copying the whole array into old when you are only going to alter a subset of it. Say the vector contains 10,000 elements. But this merge you are merging low=>5, mid=>6, high=>7 that seems like a lot of extra copying.

I would simplify this and sort into an external array, then copy only the sorted elements back.

std::vector&lt;T&gt;  sorted(high-low+1);
while(i &lt;= mid &amp;&amp; j &lt;= high) {
    if (old[j] &lt; old[i]) {
        sorted[x++] = v[j++];
    } else {
        sorted[x++] = v[i++];
    }
}
std::copy(&amp;v[i], &amp;v[mid+1],  &amp;sorted[x]); x+= (mid-i)+1;
std::copy(&amp;v[j], &amp;v[high+1], &amp;sorted[x]);

std::copy(sorted.begin(), sorted.end(), &amp;v[low]);


Since we are in the era of C++14, we can do a lot better than copying the array. We can introduce the concept of a move and move the elements around. For integers there is no difference, but if T is a big object, we would rather move it if we can.

        sorted[x++] = v[j++];

        // becomes.

        sorted[x++] = std::move(v[j++]);


Rather than passing the index and the container, just pass iterators (now it becomes easier to use the one past the end metaphor). Also, we can generalize the container to a C so that you can pass any container.

The result is:

template&lt;typename I&gt;
void merge(I low, I mid, I high) {
    I i   = low;
    I j   = mid;

    typedef typename I::value_type  value_type;
    std::vector&lt;value_type&gt; sorted(std::distance(low, high));
    auto x = sorted.begin();

    while(i &lt; mid &amp;&amp; j &lt; high) {
        if (*j &lt; *i) {
            // Use move semantics. So we don't copy expensive T object around.
            (*x) = std::move(*j); ++j;++x;
        }
        else {
            // Put the ++ inline to show difference in readability.
            // Prefer the above to this.
            (*x++) = std::move(*i++);
        }
    }
    // Don't use a manual loop when you can use an already optimized algorithm
    x = std::move(i, mid,  x);
    x = std::move(j, high, x);

    // Now move the sorted values back.
    std::move(std::begin(sorted), std::end(sorted), low);
}

template&lt;typename I&gt;
// requires std::RandomAccessIterator&lt;I&gt;           // Proposed C++17 syntax for concepts.
//       &amp;&amp; std::LessThanComparable&lt;typename I::value_type&gt;&gt;
void sort(I low, I high) {
    size size = std::distance(low, high);
    if(size &lt;= 1) {
        return;
    }
    I    mid(low)
    std::advance(mid, size/2);
    sort(low, mid);
    sort(mid, high);
    merge(low, mid, high);
}

template&lt;typename C&gt;
void sort(C&amp; v) {
    sort(std::begin(v), std::end(v));
}