#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> Merge (vector<int> & a, vector<int> & b);

vector<int> MergeSort (vector<int> a)
{
	queue<vector<int>> work;

	// Generate sub-lists of size 1, put them into queue 
	for (int i=0;i<a.size();i++)
	{
		vector<int> b;
		b.push_back (a[i]);

		work.push(b);
	}

	// while there is more than one sublists in the queue, merge them 
	while (work.size()>1)
	{
		vector<int> v1,v2;
		v1 = work.front();
		work.pop();
		v2 = work.front();
		work.pop();
		vector<int> result=Merge (v1,v2);
		work.push(result);
	}

	return work.front();
	
}

vector<int> Merge (vector<int> & a, vector<int> & b)
{
	int i=0, j=0;
	vector<int> result;

	while (i<a.size() && j<b.size())
	{
		if (a[i]<=b[j])
		{
			result.push_back(a[i]);
			i++;
		} else{
			result.push_back(b[j]);
			j++;
		}
	}

	while (i<a.size())
		result.push_back (a[i++]);
	while (j<b.size())
		result.push_back (b[j++]);
	return result;
}

int main()
{
	vector<int> a;

	for (int i=10;i>=0;i--)
		a.push_back(i);

	vector<int>  b =MergeSort (a);

	for (int i=0;i<b.size();i++)
		cout <<b[i]<<endl;

}