Mergesort sorting algorithm using recursion and vectors.

msort.cpp

#include <vector>
#include <iostream>
using namespace std;

void msort(vector<int>&);
void merge(vector<int>&, vector<int>&, vector<int>&);
void print(vector<int>&);

int main(int argc, char* argv[]){
    int d[]  = { 1, 3, 5, 4, 12, 23, 11, 12, 0};
    vector<int> x(begin(d), end(d));
    msort(x);
    print(x);
    cin.get();
    return 0;
}

void print(vector<int> &x){
    for( auto i = x.begin(); i != x.end(); ++i){
        cout << *i << " ";
    }
    cout << endl;
}

void msort(vector<int>& x){
    if( x.size() < 2 ) return;
    int mid = x.size()/2;

    // split vector
    vector<int> left(x.begin(), x.begin()+mid);
    vector<int> right(x.begin()+mid, x.end());

    // recursively call merge sort
    // on both sides
    msort(left);
    msort(right);

    //merge both sides
    merge(x, left, right);
}

void merge(vector<int> &x, vector<int> &left, vector<int> &right){
    if( x.size() != left.size()+right.size() ) return;
    auto x_i = x.begin();
    auto l_i = left.begin();
    auto r_i = right.begin();

    while( l_i != left.end() && r_i != right.end() ){
        if( *l_i < *r_i ){
            *x_i = *l_i;
            l_i++;
        }
        else{
            *x_i = *r_i;
            r_i++;
        }
        x_i++;
    }

    while( l_i != left.end() ){
        *x_i = *l_i;
        x_i++; l_i++;
    }
    while( r_i != right.end() ){
        *x_i = *r_i;        
        x_i++; r_i++;
    }
}