void merge(int a[],int p,int q,int r)
{
int n1=q-p+1;
int n2=r-q;
int *L=new int[n1+1];
int *R=new int[n2+1];
int m,n;
for(m=0;m<n1;m++)
L[m]=a[p+m];
for(n=0;n<n2;n++)
R[n]=a[q+n+1];
L[n1]=2147483647;
R[n2]=2147483647;
int i=0;
int j=0;
for(int k=p;k<=r;k++)
{
if(L[i]<=R[j])
{
a[k]=L[i];
i++;
}
else
{
a[k]=R[j];
j++;
//增加一个全局变量number，并且在此执行number+=m-i+1,就可以算序列中有几个逆序对
}
}
}
void mergesort(int a[],int p,int r)
{
int q;
if(p<r)
{
q=(p+r)/2;
mergesort(a,p,q);
mergesort(a,q+1,r);
merge(a,p,q,r);
}
}