Merge Sort algorithm

I just read and experimented with C++ implementation of the merge sort algorithm from the Wikipedia page. During the experiments I have slightly modified the source code and would like to know how much the algorithm is improved (if it is).

```
//! \brief Performs a recursive merge sort on the given vector
//! \param vec The vector to be sorted using the merge sort
//! \return The sorted resultant vector after merge sort is
//! complete.
vector merge_sort(vector& vec)
{
// Termination condition: List is completely sorted if it
// only contains a single element.
if(vec.size() == 1)
{
return vec;
}

// Determine the location of the middle element in the vector
std::vector::iterator middle = vec.begin() + (vec.size() / 2);

vector left(vec.begin(), middle);
vector right(middle, vec.end());

// Perform a merge sort on the two smaller vectors
left = merge_sort(left);
right = merge_sort(right);

return merge(vec,left, right);
}
//! \brief Merges two sorted vectors into one sorted vector
//! \param left A sorted vector of integers
//! \param right A sorted vector of integers
//! \return A sorted vector that is the result of merging two sorted
//! vectors.
vector merge(vector &vec,const vector& left, const vector& right)
{
// Fill the resultant vector with sorted results from both vectors
vector result;
unsigned left_it = 0, right_it = 0;

while(left_it < left.size() && right_it < right.size())
{
// If the left value is smaller than the right it goes next
// into the resultant vector
if(left[left_it] < right[right_it])
{
result.push_back(left[left_it]);
left_it++;
}
else
{
result.push_back(right[right_it]);
right_it++;
}
}

// Push the remaining data from both vectors onto the resultant
while(left_it < left.size())
{
result.push_back(left[left_it]);
left

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_v;

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

My Interface would have been:

template
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
void mergeSort(C& cont)
{
    mergeSort(std::begin(cont), std::end(cont));
}

StackExchange Code Review Q#90331, answer score: 4