Code

				
/*
Will Bergen
merge_sort.cpp
Implementation of Merge Sort on a randomly filled vector, timed with high res clock
chrono is from C++11, so compile with -std=gnu++11
*/

#include <iostream>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

vector<int> merge_sort(vector<int> &array);
vector<int> merge(vector<int> &l, vector<int> &r);
void pretty_print(vector<int> array);
void swap(int &in1, int &in2);
void rand_fill();


int aSize = 500; // Size of array to sort
vector<int> a; // Array to sort

int main() {
    // Randomly Fill Array:
    rand_fill();

    // Print Array before sorting:
    // pretty_print(a);

    // Time and Execute Sort:
    high_resolution_clock::time_point t1 = high_resolution_clock::now();
    a = merge_sort(a);
    high_resolution_clock::time_point t2 = high_resolution_clock::now();

    // Print Time:
    cout << "Operation Finished in " << duration_cast<microseconds>(t2-t1).count()*.000001 << " Seconds." << endl;

    // Print Array after sorting:
    // pretty_print(a);
}

/* Top-down w/ lists: */
vector<int> merge_sort(vector<int> &array) {
    // Base Case:
    if (array.size() <= 1) {
        return array;
    }

    // divide list, call it again
    vector<int> left = vector<int>();
    vector<int> right = vector<int>();
    for (int i = 0; i < array.size(); ++i)
    {
        // if i is odd add x to left, else add to right
        if (i % 2 == 1) {
            left.push_back(array[i]);
        } else {
            right.push_back(array[i]);
        }
    }

    left = merge_sort(left);
    right = merge_sort(right);

    return merge(left, right);

}

vector<int> merge(vector<int> &l, vector<int> &r){

    vector<int> result = vector<int>();
    while (!l.empty() && ! r.empty()) {
        if (l[0] <= r[0]) {
            result.push_back(l[0]);
            l.erase(l.begin());
        }  else {
            result.push_back(r[0]);
            r.erase(r.begin());
        }
    }

    while (!l.empty()) {
        result.push_back(l[0]);
        l.erase(l.begin());
    }
    while (!r.empty()) {
        result.push_back(r[0]);
        r.erase(r.begin());
    }
    return result;
}


void swap(int &in1, int &in2) {
    int temp = in1;
    in1 = in2;
    in2 = temp;
}

void rand_fill() {
    srand(time(NULL)); // Seed once
    for (int i = 0; i<aSize; i++){
        a.push_back((rand() % 100)+1); // nums 1-100
    }
}


void pretty_print(vector<int> array) {
    for (int i = 0; i < array.size()-1; ++i)
    {
        cout << array[i] << ",";
    }
    cout << array[array.size()-1] << endl;
}