作法 : Merge Sort (合併排序)

紀錄的方法是：在Merge的時候

紀錄另一個數列  比這個數列小的個數

也就是說 在做Merge的時候  實際上
它會被翻轉的次數=另一個數列小於他的數字的次數

/***********************************************************/

#include<stdlib.h>
#include<stdio.h>
int NUM[500001];
long long int ANS=0;
int MergeSort(int,int);
int Merge(int,int,int);
main()
{
  int N;
  while(scanf("%d",&N)==1&&N)
      {
         int a,b,c;
         for(a=0;a<N;a++)
            scanf("%d",&NUM[a]);
         ANS=0;
         MergeSort(0,N-1);
         printf("%lld\n",ANS);
      }
  return 0;
}
int MergeSort(int l,int h)
{
   if(l<h)
      {
         int m=(l+h)/2;
         MergeSort(l,m);
         MergeSort(m+1,h);
         Merge(l,m,h);
      }
}
int Merge(int l,int m,int h)
{
   int in1=l,in2=m+1,out=l;
   int x[500001],top=0,a,b,D=0;
   while(in1<=m&&in2<=h)
      if(NUM[in1]>NUM[in2])
           x[top++]=NUM[in2++],D++;
      else
           x[top++]=NUM[in1++],ANS+=D;
   while(in1<=m)
       x[top++]=NUM[in1++],ANS+=D;
   while(in2<=h)
       x[top++]=NUM[in2++];
   for(a=l,b=0;a<=h;a++,b++)
      NUM[a]=x[b];
}