1 public class Inversions { 2      3     public static int inversions(int [] A,int p, int r) 4     {    5          6         if(p<r) 7         { 8             int q = (int) Math.floor( (p+r)/2 ); 9             int left = inversions(A,p,q);10             int right = inversions(A,q+1,r);11             int c = combine(A,p,q,r);12             return left + right + c;13         }14         return 0;15 16     }17     public static int combine(int [] A, int p, int q, int r)18     {19         int total_inversions = 0;20         21         int n1 = q-p+1;22         int n2 = r-q;23         int [] L = new int[n1];24         int [] R = new int[n2];25         for(int i=0; i<n1; i++)26           L[i] = A[p+i];27         for(int i=0; i<n2;i++)28             R[i]=A[q+i+1];29         30         int i=0;31         int j=0;32         int counter = p;33         while(i<L.length && j<R.length)34         {35             if(L[i]<=R[j])36             {37                 A[counter]=L[i];38                 i++;39             }40             else41             {42                 A[counter]=R[j];43                 j++;44                 total_inversions += (q-(p+i)+1);45             }46             counter++;47         }48         if(i==L.length)49         {50             for(int k=j;k<R.length;k++)51                 A[counter++] = R[k];52         }53         else54         {55             for(int k=i;k<L.length;k++)56                 A[counter++] = L[k];57         }58         return total_inversions;59     }60     public static void main(String[] args) {61         int A[] = {2,3,8,6,1,7,9,1};62         int num_of_inversions = inversions(A,0,A.length-1);63         System.out.println(num_of_inversions);64     }65 }