描述
给定输入排序元素数目n和相应的n个元素，写出程序，利用内排序算法中两路合并排序算法进行排序，并输出排序最后结果的相应序列。
输入
共两行，第一行给出排序元素数目n，第二行给出n个元素，1≤n≤100000，每个元素值范围为 [0，100000)
输出
一行，输出排序结果。
样例输入
7
48 36 68 72 12 48 2
样例输出
2 12 36 48 48 68 72
#include <iostream>
#define N 100000
using namespace std;
void merge(int a[],int i1,int j1,int i2,int j2)
{
int *temp=new int[j2-i1+1];
int i=i1,j=i2,k=0;
while(i<=j1&&j<=j2)
if(a[i]<=a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
while (i<=j1) temp[k++]=a[i++];
while (j<=j2) temp[k++]=a[j++];
for(i=0;i<k;i++)
a[i1++]=temp[i];
delete[] temp;
}
void mergesort(int a[],int n)
{
int i1,j1,i2,j2;
int size=1;
while(size<n)
{
i1=0;
while(i1+size<n)
{
i2=i1+size;
j1=i2-1;
if(i2+size-1>n-1)
j2=n-1;
else
j2=i2+size-1;
merge(a,i1,j1,i2,j2);
i1=j2+1;
}
size*=2;
}
}
int main()
{
int n;
int a[N]={0};
cin>>n;
for(int k=0;k<n;k++)
cin>>a[k];
mergesort(a,n);
for(int kk=0;kk<n-1;kk++)
cout<<a[kk]<<" ";
cout<<a[n-1]<<endl;
return 0;
}