#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

void merge_sort(int *, int, int);
void merge(int*, int, int, int);


int main()
{
	int i,j, n, *v;
	FILE *f = fopen("algsort.in", "r"), *g = fopen("algsort.out", "w");
	fscanf(f,"%d", &n);
	v = (int*)malloc(sizeof(int)*n);
	for (i = 0; i < n; i++)
		fscanf(f,"%d", &v[i]);
	merge_sort(v, 0, n-1);
	for (i = 0; i < n; i++)
		fprintf(g,"%d ", v[i]);
	fclose(f); fclose(g);
	return 0;
}

void merge_sort(int * a, int p, int r)
{
	if (p < r)
	{
		int q;
		q = (p + r) / 2;
		merge_sort(a, p, q);
		merge_sort(a, q+1, r);
		merge(a, p, q, r);
		//printf("<");
	}
	return;
}


void merge(int *a, int p, int q, int r)
{
	int n1 = q - p + 1, n2 = r - q, i , j, k;
	int *L = (int*)malloc(sizeof(int)*(n1+1)), *R = (int *)malloc(sizeof(int)*(n2+1));
	L[n1] = INT_MAX;
	R[n2] = INT_MAX;
	for (i = 0; i < n1; i++)
		L[i] = a[p + i];
	for (j = 0; j < n2; j++)
		R[j] = a[q + j + 1];
	i = j = 0;
	for (k = p; k <= r; k++)
	{
		if (L[i] <= R[j])
		{
			a[k] = L[i];
			i++;
		}
		else
		{
			a[k] = R[j];
			j++;
		}
	}
	free(L);
	free(R);
	return;
}