归并排序运行时间O(N log N)，但是由于需要线性附加内存，所以很少用于主存排序。
算法核心在于以下三条语句，分治递归，分别对左半边和右半边的数组进行排序，然后把左右半边的数组一一进行比较放入数组
msort(nums,tmp,lp,center);
msort(nums,tmp,center+,rp);
merge(nums,tmp,lp,center+,rp);
下面是代码，主要包括三个函数：
void mergesort(int *nums,int n)
{
int *tmp=new int[n];
if(tmp)
{
msort(nums,tmp,,n-);
delete[]tmp;
}
}
void msort(int *nums,int*tmp,int lp,int rp)
{
int center=(lp+rp)/;
if(lp<rp)
{
msort(nums,tmp,lp,center);
msort(nums,tmp,center+,rp);
merge(nums,tmp,lp,center+,rp);
}
}
void merge(int *nums,int *tmp,int lp,int rp,int over)
{
int i=lp,j=rp,p=lp;
while(i<rp&&j<=over)
{
if(nums[i]<nums[j])
tmp[p++]=nums[i++];
else
tmp[p++]=nums[j++];
}
while(i<=rp-)
tmp[p++]=nums[i++];
while(j<=over)
tmp[p++]=nums[j++];
while(lp<=over)
{
nums[lp]=tmp[lp];
lp++;
}
}