> //归并排序  2 
> int a[1000002],b[1000002];
> __int64 num;
> void merge(int *a,int p,int q,int r)
> {int i,j=p;
>  int startA=p,endA=q-1,startB=q,endB=r;
>  while(startA<=endA&&startB<=endB)   
>  {
>   if(a[startA]<=a[startB]){b[j]=a[startA];j++;startA++;}    
>   else
>   {//1   9     10       4 5 12
>    //  startA           q  
>    b[j]=a[startB];j++;startB++;    
>    num+=q-startA;//逆序数 
>   }
>  }
>  while(startA<=endA){b[j]=a[startA];startA++;j++;}
>  while(startB<=endB){b[j]=a[startB];startB++;j++;} 
>  for(i=p;i<=r;i++)a[i]=b[i];   
> }
> void msort(int *a,int n)
> {//a[0],...a[n-1]
>   int n0,seg,lastseg,s0,i,j,m;
>    n0=n;seg=1;lastseg=1;
>    //开始有n段，每段长 seg=1，最后1段长lastseg=1 
>   num=0;
>   while(n0>=2)
>   {// 2  1  9  3  7  8 10 9  4 5 6  m=11 seg=1 lastseg=1
>    // 1 2  3 9  7 8   9 10    4 5 6  n0=5 seg0=2 lastseg=3 
>    m=n0;//两段合为1段  m段合为n0=m/2段 
>    n0/=2;s0=seg*2;
>    if(m%2==0)
>    {  //有 n0 seg  每seg 长s0 
>      for(i=1,j=0;i<=n0;i++,j+=s0)
>      { if(i<n0)merge(a,j,j+seg,j+s0-1);
>        else merge(a,j,j+seg,n-1);
>      }    
>      lastseg=seg+lastseg;
>      seg=s0;
>    }   
>    else
>    {//   1 2     3  4        5 6 7
>     for(i=1,j=0;i<=n0;i++,j+=s0)
>      merge(a,j,j+seg,j+s0-1);   
>     j=n-lastseg-s0;
>     merge(a,j,n-lastseg,n-1);    
>     seg=s0;lastseg+=s0;  
>    }
>    }
> }