CountingInversion a[i] > 3 * a[j]

The Program Demos how to Count the Inersion with Divide and Conquer Method
  1 #include
  2 using namespace std;
  3 int CountInversion(int *p, int l, int h);
  4 int Combine(int *p, int l,int m,int h);
  5 int main(){
  6   int A[6] = {112,66,4,6,3, 9};
  7   cout<  8   cout<  9   return 1;
 10 }
 11 int CountInversion(int *p, int l, int h){
 12   int M = (l + h) / 2;
 13   if(M == l){
 14     return Combine(p,l,M,h);
 15   }
 16   int CL, CH;
 17   CL = CountInversion(p,l,M);
 18   CH = CountInversion(p,M + 1,h);
 19   int CM = Combine(p,l,M,h);
 20   return CL + CH + CM;
 21 }
 22
 23 int Combine(int *p, int l,int m,int h){
 24   int l1 = m - l + 1 ;
 25   int l2 = h - m ;
 26   int INF = 65535;
 27   int *AL = new int[l1 + 1];
 28   int *AR = new int[l2 + 1];
 29   for(int i = 0; i < l1; i ++){
 30     AL[i] = p[l + i];
 31   }
 32   AL[l1] = INF;
 33   for(int j = 0; j < l2; j ++){
 34     AR[j] = p[m + j + 1];
 35   }
 36   AR[l2] = INF;
 37   int t1 = 0;
 38   int t2 = 0;
 39   for(int i = l; i <= h; i++){
 40     if(AL[t1] < AR[t2]){
 41       p[i] = AL[t1];
 42       t1 ++;
 43     }else{
 44       p[i] = AR[t2];
 45       t2 ++;
 46     }
 47   }
 48   t1 = t2 = 0;
 49   int Sum = 0;
 50   for( t1 = 0; t1 < l1; t1 ++){
 51     while(AL[t1] > 3 * AR[t2]){
 52       t2 ++;
 53     }
 54     Sum += t2;
 55   }
 56   return Sum;
 57 }