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

void merge(int *v, int n, int i, int m, int j)
{
	int a = i, b = m + 1, k = i;
	int *w = (int *)malloc(sizeof(int) * n);
	
 	while (a <= m && b <= j)
		if (v[a] < v[b])
		{
			w[k++] = v[a];
			a++;
		}
		else
		{
			w[k++] = v[b];
			b++;
		}
	while (a <= m)
	{
		w[k++] = v[a];
		a++;
	}
	while (b <= j)
	{
		w[k++] = v[b];
		b++;
	}
	for (k = i; k <= j; k++)
		v[k] = w[k];

	free(w);
}

void mergesort(int *v, int n, int i, int j)
{
	if (i < j)
	{
		int m = (i + j) / 2;
		mergesort(v, n, i, m);
		mergesort(v, n, m + 1, j);
		merge(v, n, i, m, j);
	}
}

int main()
{
	int n, *v, i;
	FILE *f, *g;

	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]);

	mergesort(v, n, 0, n - 1);
	
	for (i = 0; i < n; i++)
		fprintf(g, "%d ", v[i]);

	fclose(f);
	fclose(g);

	return 0;
}