//#include <iostream>
//#include <time.h>
#include <fstream>

using namespace std;

void MERGE(int *a, int p, int q, int r)
{
	int n1, n2;
	int v1[500005], v2[500005];
	
	n1 = q - p + 1; // determinam dimensiunea primei parti
	n2 = r - q;     // determinam dimensiunea celei de-a doua parti

	for (int i = 1; i <= n1; i++)	//copiem prima parte in vectorul temporar v1
		v1[i] = a[p + i - 1];

	for (int i = 1; i <= n2; i++)	// copiem a doua parte in vectorul temporar v2
		v2[i] = a[q + i];

	v1[n1 + 1] = v2[n2 + 1] = 999;	// pe ultima pozitite punem o valoare mare pentru a nu trece de ea

	int i = 1, j = 1;

	for (int k = p; k <= r; k++)	// facem interclasarea
		if (v1[i] <= v2[j])
		{	
			a[k] = v1[i];
			i++;
		}
		else
		{
			a[k] = v2[j];
			j++;
		}
}

void MERGE_SORT(int *a, int p, int r)
{
	int q;

	if (p < r)
	{
		q = (p + r) / 2;			// calculam jumatatea vectorului
		MERGE_SORT(a, p, q);		// aplicam procedura pe prima jumatate
		MERGE_SORT(a, q + 1, r);	// aplicam procedura pe a doua jumatate
		MERGE(a, p, q, r);			// interclasam
	}
}

int main()
{	
	ifstream in("algsort.in");
	ofstream out("algsort.out");

	int a[500005], n;

	//srand(time(NULL));						// generam n numere random
	//for (int i = 1; i <= n; i++)
	//	a[i] = rand() % 100 + 1;

	//cout << "Vector befor sorting: ";		// afisam vectorul inainte de sortare
	//for (int i = 1; i <= n; i++)
	//	cout << a[i] << " ";

	in >> n;

	for (int i = 1; i <= n; i++)
		in >> a[i];

	MERGE_SORT(a, 1, n);					// aplicam functia de sortare

	//cout << "\nVector after sorting: ";		// afisam vectorul dupa sortare
	for (int i = 1; i <= n; i++)
		out << a[i] << " ";

	//cout << "\n\n";
	//system("PAUSE");
	return 0;
}