A little practice.

gistfile1.cpp

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cassert>

using namespace std;


namespace Merge {
    void merge(vector<int>& vals, vector<int>& auxs, int beg, int mid, int end) {
        for (int i = beg; i < end; ++i) {
            auxs[i] = vals[i];
        }

        int i = beg, j = mid, c = beg;
        while (c < end) {
            if (i>=mid) {
                auxs[c++] = vals[j++];
            } else if (j>=end) {
                auxs[c++] = vals[i++];
            } else if (vals[i]<vals[j]) {
                auxs[c++] = vals[i++];
            } else {
                auxs[c++] = vals[j++];
            }
        }

        for (int i = beg; i < end; ++i) {
            vals[i] = auxs[i];
        }
    }

    vector<int> sort(const vector<int>& unsorted) {
        const int N = unsorted.size();
        vector<int> vals = unsorted;
        vector<int> auxs = unsorted;

        for (int w = 1; w < N; w*=2) {
            for (int i = 0; (i+w) < N; i+=(w*2)) {
                Merge::merge(vals, auxs, i, i+w, min(i+w*2, N));
            }
        }

        return vals;
    }
};


namespace Quick {
    void partition(vector<int>& vals, int beg, int end) {
        if (beg>=end) {
            return;
        }

        swap(vals[beg], vals[end]);
        const int pivot = vals[end];

        int s = beg;
        for (int i = beg; i < end; ++i) {
            if (vals[i] < pivot) {
                swap(vals[s++], vals[i]);
            }
        }
        swap(vals[s], vals[end]);

        partition(vals, beg, s-1);
        partition(vals, s+1, end);
    }

    vector<int> sort(const vector<int>& unsorted) {
        int N = unsorted.size();
        vector<int> vals = unsorted;
        partition(vals, 0, N-1);

        return vals;
    }
}


int main(int argc, char *argv[]) {
    const int N = 100;

    vector<int> vals;
    for (int i = 0; i < N; ++i) {
        vals.push_back(rand()%N);
        cout << vals.back() << " ";
    }
    cout << endl;

    vector<int> expected = vals;
    sort(expected.begin(), expected.end());
    for (int i = 0; i < expected.size(); ++i) {
        cout << expected[i] << " ";
    }
    cout << endl;

    vector<int> actual = Merge::sort(vals);
    for (int i = 0; i < actual.size(); ++i) {
        cout << actual[i] << " ";
    }
    cout << endl;
    assert(actual==expected);

    vector<int> actual2 = Quick::sort(vals);
    for (int i = 0; i < actual2.size(); ++i) {
        cout << actual2[i] << " ";
    }
    cout << endl;
    assert(actual2==expected);
}