/*
 * =====================================================================================
 *
 *       Filename:  mergesort.cpp
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  07/15/13 13:34:21
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (), 
 *   Organization:  
 *
 * =====================================================================================
 */

#include <iostream>
#include <cstdio>
#define INF 0xfffffff
#define NMAX 500001

using namespace std;

void merge(int* v, int low, int mid, int high)
{
	int L[NMAX / 2 + 1], R[NMAX / 2 + 1], i, j;
	int n1 = mid - low + 1;
	int n2 = high - mid;

	for (i = 1; i <= n1; i++)
		L[i] = v[low + i - 1];
	for (i = 1; i <= n2; i++)
		R[i] = v[mid + i];
								// both L and R are already sortde, being bottom up
							// interclasare
	L[n1 + 1] = INF; 
	R[n2+1] = INF;	

	i = j = 1; 
	for (int k = low; k <= high; k++)
		if (L[i] < R[j])
		{
			v[k] = L[i];
			i++;
		}
		else
		{
			v[k] = R[j];
			j++;
		}
}


void mergeSort(int* v, int low, int high)
{
	if (low < high)
	{
		int mid = (low + high) / 2;
		mergeSort(v, low, mid);
		mergeSort(v, mid + 1, high);
		merge(v, low, mid, high);
	}
}

int main()
{
	FILE *in, *out;
	int N, a[NMAX];
	
	in = fopen("algsort.in","r");
	out = fopen("algsort.out", "w");
	fscanf(in, "%d", &N);
	for (int i = 1; i <= N; i++)
		fscanf(in, "%d", &a[i]);

	mergeSort(a, 1, N);

	for (int i = 1; i <= N; i++)
		fprintf(out, "%d ", a[i]);

	fclose(in);
	fclose(out);
	return 0;
}