#include <vector>
#include <iostream>
using namespace std;


vector<int>  Merge(vector<int>& a, vector<int>& b) {
	unsigned long long ap = 0, bp = 0;
	vector<int> c;
	while (ap<a.size() and bp < b.size())
	{
		if (a[ap] < b[bp]) {
			c.push_back(a[ap]);
			ap += 1;
		}
		else{
			c.push_back(b[bp]);
			bp += 1;
		}
	}
	if (bp == b.size()) {
		for(unsigned long long i=ap;i<a.size();i++) c.push_back(a[i]);
	}
	if (ap == a.size()) for (unsigned long long i = bp; i < b.size(); i++) c.push_back(b[i]);
	return c;
}

void MergeSort(vector<int>& a) {
	if (a.size() > 1) {
		vector<int> b, c;
		for (unsigned int i = 0; i < a.size() / 2; i += 1)  b.push_back(a[i]);
		for (unsigned int i = a.size() / 2; i < a.size(); i++) c.push_back(a[i]);
		MergeSort(b);
		MergeSort(c);
		a =Merge(b, c);
	}
}


int main()
{
	vector<int> a;
	for (int i = 0; i < 5; i++) {
		a.push_back(5-i);
	}
	for (int i = 0; i < 5; i++) cout << a[i] << ' ';
	MergeSort(a);
	cout << '\n';
	for (int i = 0; i < 5; i++) cout << a[i] << ' ';
	int j;
	cin >> j;
}