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

void read(FILE *f, int *a, int N)
{
	int i;

	for (i = 0; i < N; i++)
		fscanf(f, "%d", a + i);
}

void print(FILE *g, int *a, int N)
{
	int i;

	for (i = 0; i < N; i++)
		fprintf(g, "%d ", a[i]);
}

void swap(int *a, int i, int j)
{
	int tmp = a[i];
	   a[i] = a[j];
	   a[j] = tmp;
}

void merge(int *a, int start, int end)
{
	int mid = (start + end)/2, i, j, k;
	int *tmp = malloc((start + end + 1) * sizeof(int));

	i = start;
	j = mid + 1;
	k = 0;

	while (i <= mid && j <= end) {
		if (a[i] < a[j])
			tmp[k++] = a[i++];
		else
			tmp[k++] = a[j++];
	}

	while (i <= mid)
		tmp[k++] = a[i++];

	while (j <= end)
		tmp[k++] = a[j++];

	for (i = 0; i < k; i++)
		a[start + i] = tmp[i];

	free(tmp);
}


void mergeSort(int *a, int start, int end)
{
	int mid;

	if (start < end) {
		mid = (start + end)/2;
		mergeSort(a, start, mid);
		mergeSort(a, mid + 1, end);
		merge(a, start, end);
	}
}

int main()
{
	srand(time(NULL));
	FILE *f = NULL , *g = NULL;
	int N, *a = NULL;
	f = fopen("algsort.in", "rt");
	g = fopen("algsort.out", "wt");

	fscanf(f, "%d", &N);
	a = malloc(N * sizeof(int));

	read(f, a, N);
	mergeSort(a, 0, N-1);
	print(g, a, N);

	fclose(f);
	fclose(g);
	free(a);
	return 0;
}