mergesort.cpp

#include <iostream>
#include <vector>

using namespace std;

// clang++ -std=c++11 -stdlib=libc++ -Weverything mergesort.cpp

vector<int> merge_sort(vector<int> v);
vector<int> merge(vector<int> left, vector<int> right);
ostream& operator << (ostream& os, vector<int> v);

int main()
{
    cout << "unit test of merge() function:" << endl;
    cout << merge({1,2,3}, {4,5}) << endl;
    cout << merge({4,5}, {1,2,3}) << endl;
    cout << merge({1,3,4,7}, {2,4,7,9}) << endl;

    cout << "unit test of merge_sort() function:" << endl;
    cout << merge_sort({1,2,3,4,5,6,7}) << endl;
    cout << merge_sort({7,6,5,4,3,2,1,0}) << endl;
    cout << merge_sort({3,9,5,1,6}) << endl;
    cout << merge_sort({99,88,77,66,55,44,33,22,11,1}) << endl;
}

vector<int> merge_sort(vector<int> v)
{
    if(v.size() == 1)
        return v;

    size_t middle = v.size() / 2;
    size_t end = v.size();

    vector<int> left (&v[0], &v[middle]);
    vector<int> right (&v[middle], &v[end]);
    //cout << "middle = " << middle << ", before = " << left << "," << right << endl;

    left = merge_sort(left);
    right = merge_sort(right);
    //cout << "after = " << left << "," << right << endl;

    return merge(left, right);
}

vector<int> merge(vector<int> left, vector<int> right)
{
    // Preconditions: left/right MUST be sorted.

    vector<int> result;
    while(not left.empty() && not right.empty())
    {
        if(left[0] <= right[0])
        {
            result.push_back(left[0]);
            left.erase(left.begin());
        }
        else
        {
            result.push_back(right[0]);
            right.erase(right.begin());
        }
    }

    for(size_t i = 0; i < left.size(); i++)
        result.push_back(left[i]);

    for(size_t i = 0; i < right.size(); i++)
        result.push_back(right[i]);

    return result;
}

ostream& operator << (ostream& os, vector<int> v)
{
    os << "[";
    for(size_t i = 0; i < v.size(); i++)
    {
        os << v[i];
        if(i != v.size()-1)
            os << ", ";
    }
    os << "]";
    return os;
}