#include <fstream>

void osszefesul(int tomb[], int bal, int kozep, int jobb){
	int *temp = new int[jobb - bal + 1];
	int indexTemp = 0, indexBal = bal, indexJobb = kozep + 1;
	while(indexBal <= kozep && indexJobb <= jobb){
		if(tomb[indexBal] <= tomb[indexJobb])
			temp[indexTemp++] = tomb[indexBal++];
		else
			temp[indexTemp++] = tomb[indexJobb++];
	}
	while(indexBal <= kozep)
		temp[indexTemp++] = tomb[indexBal++];
	while(indexJobb <= jobb)
		temp[indexTemp++] = tomb[indexJobb++];
	for(int i = 0; i < indexTemp; i++)
		tomb[bal + i] = temp[i];
	delete[] temp;
	return;
}

void mergesort(int tomb[], int bal, int jobb){
	if(bal >= jobb)
		return;
	int kozep = (bal + jobb) / 2;
	mergesort(tomb, bal, kozep);
	mergesort(tomb, kozep + 1, jobb);
	osszefesul(tomb, bal, kozep, jobb);
	return;
}

int main(){
	std::ifstream bem("algsort.in");
	int n;
	bem >> n;
	int *tomb = new int[n];
	for(int i = 0; i < n; i++) bem >> tomb[i];
	bem.close();

	mergesort(tomb, 0, n - 1);

	std::ofstream kim("algsort.out");
	for(int i = 0; i < n; i++) kim << tomb[i] << " ";
	delete[] tomb;
}