合并排序

/**b[l:r]复制到a[l:r]中 **/
void copy(int a[],int b[],int l,int r)
{
    for(; l<=r; l++)
        a[l]=b[l];
}

void MergeSort(int a[],int left,int right)
{
    if(left<right)   //至少有2个元素
    {
        int b[N];
        int i=(left+right)/2; // 取中点
        MergeSort(a,left,i);
        MergeSort(a,i+1,right);
        Merge(a,b,left,i,right);    //合并到数组b
        copy(a,b,left,right);       //复制回数组
    }
}

/**
对两个已排序的数组进行合并排序。
合并c[l:m]和c[m+1:r]到d[l:r]
**/
void Merge(int c[],int d[],int l,int m,int r)
{
    int i =l,j=m+1,k=l;
    while((i<=m)&&(j<=r))
        if(c[i]<=c[j])d[k++]=c[i++];
        else d[k++]=c[j++];
    if(i>m)for(int q=j; q<=r; q++) d[k++]=c[q];
    else for(int q=i; i<=m; i++) d[k++]=c[q];
}