#include "iostream.h"
using namespace std;
void merge(int A[], int Tmp[], int leftStart,int rightStart, int rightEnd){
	int number = rightEnd-leftStart+1;
	int leftEnd = rightStart-1;
	int left=leftStart;
	
	int right = rightStart;
	int pos= leftStart;
	
	while(left<=leftEnd&&right<=rightEnd){
		if(A[left]<=A[right]){
			Tmp[pos++]=A[left++];
		}else{
			Tmp[pos++]=A[right++];
		}
	}
	while(left<=leftEnd){
		Tmp[pos++]=A[left++];
	}
	while(right<=rightEnd){
		Tmp[pos++]=A[right++];
	}
	int i=0;
	//记得把Tmp拷回A，保证A有序 
	while(i<number){
		A[rightEnd]=Tmp[rightEnd];
		rightEnd--;
		i++;
	}
}
void msort(int A[], int Tmp[], int left,int right){
	if(left<right){
		int center = (left+right)/2;
		msort(A,Tmp,left,center);
		msort(A,Tmp,center+1,right);
		merge(A,Tmp,left,center+1,right);
		
	}
}
void mergeSort(int A[], int N){
	int *Tmp = (int*)malloc(sizeof(int)*N);
	if(Tmp){
		msort(A,Tmp,0,N-1);
	}else{
		cout<<"No space"<<endl;
	}
}

int main()
{
	int A[100];
	int N;
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>A[i];
	}	
	mergeSort(A,N);
	for(int i=0;i<N;i++){
		cout<<A[i]<<" ";
	}
	cout<<endl;
	return 0;
}

归并排序