#include <stdio.h>

int a[1000000], b[1000000];

void mergesort(int l, int r)
{
	if(l+1 == r) return;
	int m = (l+r)/2;
	mergesort(l,m);
	mergesort(m,r);
	int i=l, j=m, k=0;
	while(1)
	{
		if(i == m && j == r) break;
		else if(i == m) b[k++] = a[j++];
		else if(j == r) b[k++] = a[i++];
		else if(a[i] < a[j]) b[k++] = a[i++];
		else b[k++] = a[j++];
	}
	for(i=l;i<r;i++) a[i] = b[i-l];
}

int main() {
	mergesort(0,n); //O primeiro valor é fixo (posicao com a qual sera comparado)
	int i;
	for(i=0; i<n; i++) printf("%d ",a[i]);
	printf("\n");
	return 0;
}