void merge_sort(int *A,int x,int y,int *T)
{
    if(y-x>1)
    {
        int m=x+(y-x)/2;//划分
        int p=x,q=m,i=x;
        merge_sort(A,x,m,T);  //递归求解
        merge_sort(A,m,y,T);   //递归求解
        while(p<m||q<y)
        {
            if(q>=y||(p<m&&A[p]<=A[q])) T[i++]=A[p++];   //从左半数组复制到临时空间
            else T[i++]=A[q++];   //从右半数组复制到临时空间
        }
        for(int i=x;i<y;i++) A[i]=T[i];   //从辅助空间复制回A数组
    }
}

未完待续……

逆序对问题：给一列数，a1,a2,…,an,求它的逆序对数，即有多少个有序对（i,j）,使得i<j但ai>aj,n可高达10^6

void merge_sort(int *A,int x,int y,int *T)
{
    if(y-x>1)
    {
        int m=x+(y-x)/2;//划分
        int p=x,q=m,i=x;
        merge_sort(A,x,m,T);  //递归求解
        merge_sort(A,m,y,T);   //递归求解
        while(p<m||q<y)
        {
            if(q>=y||(p<m&&A[p]<=A[q])) T[i++]=A[p++];   //从左半数组复制到临时空间
            else 
            {
                T[i++]=A[q++]; 
                cnt+=m-p;  //cnt调用之前清零
            }  //从右半数组复制到临时空间
        }
        for(int i=x;i<y;i++) A[i]=T[i];   //从辅助空间复制回A数组
    }
}