#include <fstream>
#include <cstdlib>
#include <ctime>
#include <iostream>
#define SIZE 500000
#define RANDOM(a, b) ((a) + (rand() % ((b) - (a) + 1)))
#define INSERTION_SORT_TRESHOLD 50
using namespace std;

void swap(int A[], int i, int j)
{
	int aux = A[i];
	A[i] = A[j];
	A[j] = aux;
}

void insertion_sort(int A[], int left, int right)
{
	for (int i = left + 1; i <= right; ++i) 
	{
		int e = A[i];
		int j = i;
		while (j > left && A[j-1] > e) 
		{
			A[j] = A[j-1];
			--j;
		}
			
		A[j] = e;
	}
}

int partition(int A[], int left, int right)
{
	int randomIndex = RANDOM(left, right);
	
	swap(A, left, randomIndex);
	int pivot = A[left];
	
	while (left <= right)
	{
		while (A[left] < pivot) ++left;
		while (A[right] > pivot) --right;
		
		if (left <= right) swap(A, left++, right--);
	}
	return right;
}

void quicksort(int A[], int left, int right)
{
	if (left < right) 
	{
		// Optional
		if (right - left < INSERTION_SORT_TRESHOLD) 
		{
			insertion_sort(A, left, right);
			return;
		}
	
		int p = partition(A, left, right);
		quicksort(A, left, p);
		quicksort(A, p + 1, right);
	}
}

void merge(int TO[], int FROM[], int left, int mid, int right)
{
	int i = left;
	int j = mid + 1;
	
	int k = left;
	
	while (i <= mid && j <= right)
	{
		if (FROM[j] < FROM[i]) TO[k++] = FROM[j++];
		else TO[k++] = FROM[i++];
	}
	
	while (i <= mid) TO[k++] = FROM[i++];
	while (j <= right) TO[k++] = FROM[j++];
}

void mergesort(int A[], int B[], int left, int right)
{
	if (left < right)
	{
		// Optional
		if ((right - left) < INSERTION_SORT_TRESHOLD) 
		{
			insertion_sort(A, left, right);
			return;
		}

		int mid = left + (right - left) / 2;
		
		mergesort(B, A, left, mid);
		mergesort(B, A, mid + 1, right);
		
		merge(A, B, left, mid, right);
	}
}

void mergesort(int A[], int n)
{
	int* B = new int[n];
	
	for (int i = 0; i < n; ++i)
		B[i] = A[i];
	
	mergesort(A, B, 0, n-1);
}

int main()
{
	ifstream ifs("algsort.in");
	ofstream ofs("algsort.out");
	
	srand(time(NULL));
	
	int A[SIZE], n;
	ifs >> n;
	
	for (int i = 0; i < n; ++i)	
		ifs >> A[i];
	
	//insertion_sort(A, 0, n-1);
	//quicksort(A, 0, n-1);
	mergesort(A, n);
	
	for (int i = 0; i < n; ++i)
		ofs << A[i] << " ";
	
	return 0;
}