Merge Sort algorithm

Question

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<int> merge_sort(vector<int>& 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<int>::iterator middle = vec.begin() + (vec.size() / 2);

    vector<int> left(vec.begin(), middle);
    vector<int> 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<int> merge(vector<int> &vec,const vector<int>& left, const vector<int>& right)
{
    // Fill the resultant vector with sorted results from both vectors
    vector<int> 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_it++;
    }

    while(right_it < right.size())
    {
        result.push_back(right[right_it]);
        right_it++;
    }
    //show merge process..
      int i;
      for(i=0;i<result.size();i++)
         {                                
         cout<<result[i]<<" ";
         }
    // break each line for display purposes..
        cout<<"***********"<<endl; 

    //take a source vector and parse the result to it. then return it.  
    vec = result;               
    return vec;
}

The following is my code:

typedef std::vector<int> int_v;

int_v Merge(int_v& vec, int_v& l, int_v& r) {
  int_v res;
  res.reserve(l.size() + r.size());
  unsigned int li = 0;
  unsigned int ri = 0;
  if (l.size() > 1 && (l[l.size()-1] < r[0])) {
    res.insert(res.end(), l.begin(), l.end());
    res.insert(res.end(), r.begin(), r.end());
    return res;
  }
  while (li < l.size() && ri < r.size()) {
    if (l[li] < r[ri]) {
      res.push_back(l[li++]);
    } else {
      res.push_back(r[ri++]);
    }
  }
  while (li < l.size()) {
      res.push_back(l[li++]);
  }
  while (ri < r.size()) {
      res.push_back(r[ri++]);
  }
  vec = res;
  return vec;
}

int_v MergeSort(int_v& v) {
  if (1 == v.size()) {
    return v;
  }
  int_v::iterator m = v.begin() + v.size()/2;
  int_v l(v.begin(), m);
  int_v r(m, v.end());

  l = MergeSort(l);
  r = MergeSort(r);
  return Merge(v, l, r);
}

The modifications are:

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

This will help to avoid relocation of the vector each time when there will need to double the size to be able to store the next element.

  if (l.size() > 1 && (l[l.size()-1] < r[0])) {
    res.insert(res.end(), l.begin(), l.end());
    res.insert(res.end(), r.begin(), r.end());
    return res;
  }

I think this will help to avoid the 'while' loops when just concatenation of two sides is enough.

Running both versions Wikipedia's one and mine for five million randomly generated integers produces the following differences:

Wikipedia's example:

time ./a.out 
real    0m26.278s
user    0m26.205s
sys 0m0.064s

Mine:

time ./a.out 
real    0m22.129s
user    0m22.026s
sys 0m0.092s

Answer 1

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));
}

Answer 2

If your goal is speed then simple arrays will be fastest. Also it's sufficient to create a new array only once at the start of the algorithm. Here is some C code that's reasonably fast. Needs only 0.5s for 5 million numbers.

time ./a.out

real  0m0.528s
user  0m0.466s
sys   0m0.061s

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void bubbleSort(int *a, int start, int end) {
    int i, x, y;
    end--;
    while(end > start) {
        for(i = start; i < end; i++) {
            x = a[i], y = a[i+1];
            if(x > y) {a[i] = y; a[i+1] = x;}
        }
        end--;
    }
}

void merge(int *a, int start, int *a2, int start2, int mid, int end) {
    int i, i1, i2;
    i = start, i1 = start2, i2 = mid;
    while(i1 < mid && i2 < end) {
        if(a2[i1] <= a2[i2]) a[i++] = a2[i1++];
        else a[i++] = a2[i2++];
    }
    while(i1 < mid) {
        a[i++] = a2[i1++];
    }
    while(i2 < end) {
        a[i++] = a2[i2++];
    }
};

void _mergeSort(int *a1, int *a2, int start, int end) {
    int mid;
    if(end - start < 2) return;
    if(end - start < 8) { bubbleSort(a1, start, end); return; }
    mid = (start + end)/2;
    _mergeSort(a2, a1, start, mid);
    _mergeSort(a2, a1, mid, end);
    merge(a1, start, a2, start, mid, end);
};

void mergeSort(int *a, int length) {
    int *a2 = malloc(sizeof(int) * length);
    memcpy(a2, a, sizeof(int) * length);
    _mergeSort(a, a2, 0, length);
    free(a2);
};

void fillRandNumbers(int *a, int start, int end, int low, int high) {
  int i;
  for(i = start; i < end; i++) {
    a[i] = rand() % (high - low) + low;
  }
}

void main() {
  int i, N = 5000000;
  long sum;
  int *nums = malloc(sizeof(int) * N);
  srand(time(NULL));
  fillRandNumbers(nums, 0, N, 1, N + 1);

  mergeSort(nums, N);

  free(nums);
}