#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;
}