#include <iostream>
using namespace std;
template <class Type>
void MergeSort(Type a[],int n)
{
/*    Type *b=new Type[right-left];
    if(left<right) //至少有两个元素
    {
        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);   //复制回数组a
    }
*/
    Type *b=new Type[n];
    int s=1;
    while(s<n)
    {
        MergePass(a,b,s,n);
        s+=s;
        MergePass(b,a,s,n);
        s+=s;
    }
}
template<class Type>
void MergePass(Type x[],Type y[],int s,int n)
{
    int i=0;
    while(i<=n-2*s)
    {
        Merge(x,y,i,i+s-1,i+2*s-1);
        i=i+2*s;
    }
    if(i+s<n)
        Merge(x,y,i,i+s-1,n-1);
    else
        for(int j=i;j<=n-1;j++)
            y[j]=x[j];
}
template <class Type>
void Merge(Type c[],Type 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;q<=m;q++)
                d[k++]=c[q];
}
void main()
{
    int m;      //数组的长度是m
    cout<<"请输入数组的长度：";
    cin>>m;
    int *a;
    a=new int [m];
    cout<<"输入数组：";
    for(int c=0;c<m;c++)
        cin>>*(a+c);
    MergeSort(a,m);
    cout<<"排序后的数组是：";
    for(int d=0;d<m;d++)
        cout<<*(a+d)<<" ";
    cout<<endl;
}


MergePass（）函数是干什么的。。。不懂~~~求解答