count-merge.h

算法类

inline void COUNT_MERGE(int* A,int p,int q,int r,int& count)
{
  int* array1=new int[q-p+1];
  int* array2=new int[r-q];
  const int count1=q-p+1;
  const int count2=r-q;
  for(int i=p;i!=q+1;++i)
    array1[i-p]=A[i];
  for(int i=q+1;i!=r+1;++i)
    array2[i-q-1]=A[i];
  int j=0,k=0;
  for(int i=p;i!=r+1;++i)
    {
      if(j == count1)
	{
	  A[i]=array2[k];
	  ++k;
	}
      else if(k == count2)
	{
	  A[i]=array1[j];
	  ++j;
	}
      else if(array1[j] >= array2[k])
	{
	  A[i]=array2[k];
	  count+=count1-j;
	  ++k;
	}
      else
	{
	  A[i]=array1[j];
	  ++j;
	}
    }
}