#include<iostream.h>
#include<conio.h>
void merge(int *arr,int p,int q,int r)
{
	int n1=q-p+1;
	int n2=r-q;
	int *arr1=new int[n1];
	int *arr2=new int [n2];
	for(int i=0;i<n1;i++)
	{
		arr1[i]=arr[i];
	}
	for(int j=0;j<n2;j++)
	{
		arr2[j]=arr[j+q+1];
	}
	i=j=0;
	for(int m=p;m<=r;m++)
	{
		if(arr1[i]<=arr2[j])
		{
			arr[m]=arr1[i];
			i++;
		}
		else
		{
			arr[m]=arr2[j];
			j++;
		}
		if(i==n1 || j==n2)
			break;
	}
    
	while(i != n1)
		arr[++m]=arr1[i++];
	while(j != n2)
		arr[++m]=arr2[j++];
}


//**************************************************	
void merge_sort(int *arr,int p, int r)
{
	int q;
	if(p<r)
	{
		q=((p+r)/2);
	   
		merge_sort(arr,p,q);
		merge_sort(arr,q+1,r);
		merge(arr,p,q,r);
	}
}
//***************************************************
int main()
{
    cout<<"enter length:"<<endl;
	int n;
	cin>>n;
	int *arr=new int[ n];
	for(int i=0;i<n;i++)
	{
		cout<<"enter arr["<<i<<"]"<<"="<<endl;
		cin>>arr[i];
	}
	merge_sort(arr,0,n-1);
    for(int j=0;j<n;j++)
	{
		cout<<"  "<<arr[j];
	}

	getch();
	return 0;

}