#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
int arr[1000002];
typedef struct qsortstruct
{
	int left;
	int right;

}qsortstruct;

void * qsorthelper (void * a);

print(int i, int j)
{
	int k;
	for(k = i; k < j; k++)
		printf("%d ", arr[k]);
	printf("\n");
}

void swap(int i, int j)
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
	return;
}

int partition(int start, int end, int pivot)
{
	int i, pivotindex = pivot, pivotvalue = arr[pivot];
	swap(end, pivot);
	int storeindex = start;
	for(i = start; i < end; i++)
	{
		if(arr[i] < pivotvalue)
		{
			swap(i, storeindex);
			storeindex++;
		}
	}
	swap(end, storeindex);
	return storeindex;
}

//to find the median value for choosing the pivot element
int median(int a, int b, int c)
{
	if(arr[a] < arr[b])
	{
		if(arr[a] >= arr[c])
			a;
		else if(arr[c] > arr[b])
		    	b;
	}

	else if(arr[a] >= arr[b])
	{
		if(arr[c] >= arr[a])
			return a;
		else if(arr[b] >= arr[c])
			return b;
	}
	return c;
}

void quicksort(int start, int end)
{
	int i, pivot;
	if(start >= end)
		return;
	pivot = median(start, end, start + (end-start)/2);
	int index = partition(start, end, pivot);

	//the structure to pass to the thread entry point(qsorthelper) as void argument
	qsortstruct varl;
	varl.left = start;
	varl.right = index - 1;
	pthread_t threads1;

	//sort left half of pivot in another thread in parallel
	pthread_create(&threads1, NULL, qsorthelper, &varl);

	quicksort(index + 1, end);
	//Wait for both to finish
	pthread_join(threads1, NULL);
}

//function for thread to start another quicksort in parallel
void * qsorthelper (void * a)
{
	qsortstruct * init = ((qsortstruct *)a);
	int start = init -> left;
	int end = init -> right;
	quicksort(start,end);
	return NULL;
}

int main()
{
	int n;
	//scan size of input elements
	scanf("%d", &n);
	int i, j;
	for(i = 0; i < n; i++)
		scanf("%d", &arr[i]);
	quicksort(0, n - 1);
	print(0,n);

	return 0;
}