tshm
6/4/2014 - 9:29 AM

mergesort.cpp

#include "stdafx.h"
#include <vector>
#include <random>

void randomize(std::vector<int> &vec) {
	for ( auto& v : vec ) {
		v = std::rand();
	}
}

std::vector<int> merge(std::vector<int> &vec1, std::vector<int> &vec2) {
	auto out = std::vector<int>(vec1.size() + vec2.size());
	auto k = out.begin();
	auto i = vec1.begin();
	auto j = vec2.begin();
	while (true) {
		if (*i < *j) {
			*(k++)=(*i);
			if (++i == vec1.end()) break;
		} else {
			*(k++)=(*j);
			if (++j == vec2.end()) break;
		}
	}
	for (; i<vec1.end(); i++) *(k++)=(*i);
	for (; j<vec2.end(); j++) *(k++)=(*j);
	return out;
}

std::vector<int> mergesort(std::vector<int> &vec) {
	int length = vec.size();
	if (length == 1) return vec;
	if (length == 2) {
		if (vec[0] > vec[1]) {
			auto tmp = vec[0];
			vec[0] = vec[1];
			vec[1] = tmp;
		}
		return vec;
	}
	auto vec1 = mergesort(std::vector<int>(vec.begin(), vec.begin() + length /2));
	auto vec2 = mergesort(std::vector<int>(vec.begin() + length /2, vec.end()));
	return merge(vec1, vec2);
}

int main(int argc, char* argv[])
{
	auto input = std::vector<int>(100, 0);
	randomize( input );

	auto output = mergesort( input );

	for ( const auto &v : output ) {
		printf("%d\n", v);
	}
	return 0;
}