#include <fstream>
#include <vector>

using namespace std;

void Interclaseaza(int *vec, int l, int m, int r)
{
	int *aux = new int[r - l + 1];

	int i = l, j = m + 1, auxIt = 0;

	while (i <= m && j <= r)
	{
		if (vec[i] < vec[j])
		{
			aux[auxIt] = vec[i];
			i++;
			auxIt++;
		}
		else
		{
			aux[auxIt] = vec[j];
			j++;
			auxIt++;
		}
	}

	while (i <= m && j > r)
	{
		aux[auxIt] = vec[i];
		i++;
		auxIt++;
	}

	while (i > m && j <= r)
	{
		aux[auxIt] = vec[j];
		j++;
		auxIt++;
	}

	for (int i = 0; i <= r - l; i++)
	{
		vec[i + l] = aux[i];
	}

	delete[] aux;
}

//functia pentru mergesort
void MergeSort(int *vec, int l, int r)
{
	if (l == r)
		return;

	int mid = (l + r) / 2;

	MergeSort(vec, l, mid);
	MergeSort(vec, mid + 1, r);
	Interclaseaza(vec, l, mid, r);
}

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

	int n;
	IN >> n;

	int *vec = new int[n];

	for (int i = 0; i < n; i++)
	{
		IN >> vec[i];
	}

	MergeSort(vec, 0, n - 1);

	for (int i = 0; i < n; i++)
	{
		OUT << vec[i] << " ";
	}

	OUT << "\n";

	delete[] vec;

	return 0;
}