#include<iostream.h>

void merge(int array[],int temparray[],int left,int middle,int right)
{
	for(int j=left;j<=right;j++)
		temparray[j]=array[j];
	int index1=left;
	int index2=middle+1;
	int i=left;
	while((index1<=middle)&&(index2<=right))
	{
		if(temparray[index1]<=temparray[index2])
		{
			array[i++]=temparray[index1++];
		}
		else
		{
			array[i++]=temparray[index2++];
		}
	}
	while(index1<=middle)
		array[i++]=temparray[index1++];
	while(index2<=right)
		array[i++]=temparray[index2++];
}



void sort(int * array,int * temparray,int left,int right)
{
	if(left<right)
	{
		int middle=(left+right)/2;
		sort(array,temparray,left,middle);
		sort(array,temparray,middle+1,right);
		merge(array,temparray,left,right,middle);
	}
}
void main()
{
	cout<<"please input the number of integers:"<<endl;
	int num;
	cin>>num;
	int * array=new int[num];
	cout<<"please input the integers:"<<endl;
	int i;
	for(i=0;i<num;i++)
	{
		cin>>array[i];
	}
	int * temparray=new int[num];
	sort(array,temparray,0,num-1);
	
	for(i=0;i<num;i++)
	{
		cout<<array[i]<<" "<<endl;
	}
}