Return to Revisions

Overall comment.

It would have been better if you had used iterators to implement the sort. It's a lot more versatile than using a specific container.

Memory Allocation

Your implementation requires a lot of dynamic memory allocation.

int_v::iterator m = v.begin() + v.size()/2;
int_v l(v.begin(), m);
int_v r(m, v.end());

Each recursive call makes a copy of the data to be merged. So we get this progression:

    n + n/2 + n/4 + n/8 + n/16 ....
    =>  n(1 + 1/2 + 1/4 + 1/8 + 1/16.....)
    =>  2n

So you are using \$2n\$ size of data just through calling MergeSort and it is being allocated and deallocated as the std::vector is being used then destroyed on return.

In Addition you are doing another memory allocation in Merge():

int_v res;
res.reserve(l.size() + r.size());

Note

By using iterators rather than containers, it becomes easy to avoid some of this copying. You just pass the ranges of the containers and do it in-place.

Prefer to move rather than to copy

vec = res;

Here you are copying the contents of the array. Arrays can be moved (this means it swaps a couple of pointers rather than copying all the data). Since you are not using res after this point you should move it.

vec = std::move(res);

User defined types usually start with a capital

typedef std::vector<int> int_v;

To distinguish user defined types and objects. Proceed types with an initial capital letter.

My Interface would have been:

template<typename I>
void mergeSort(I begin, I end)
{
    auto size = std::distance(begin, end);
    auto mid  = begin;
    std::advance(mid, size/2);

    mergeSort(begin, mid);
    mergeSort(mid, end);
    merge(begin, mid, end);
}
template<typename C>
void mergeSort(C& cont)
{
    mergeSort(std::begin(cont), std::end(cont));
}