A very naiive mergesort

gistfile1.txt

/*
  This highlights the problems with big O notation. This algorithm is
 a naiive mergesort implementation. When analyzed its clear to see it is O(nlogn)
 however, this implementation takesd over 5 seconds to sort 2.5m int's where
 a well done implementation can do it in 1/10th the time.
*/

vector<int> merge(vector<int>& a, vector<int>& b) {
	int i = 0, j = 0;
	vector<int> res;
	while (i < a.size() && j < b.size()) {
		if (a[i] < b[j]) {
			res.push_back(a[i++]);
		} else {
			res.push_back(b[j++]);
		}
	}
	while (i < a.size()) res.push_back(a[i++]);
	while (j < b.size()) res.push_back(b[j++]);
	return res;
}

void mergesort(vector<int>& in) {
	if (in.size() <= 1)
		return;
	vector<int> front, back;
	int m = in.size() / 2;
	for (int i = 0; i < in.size(); i++) {
		if (i < m) front.push_back(in[i]);
		else back.push_back(in[i]);
	}
	mergesort(front);
	mergesort(back);
	in = merge(front, back);
}