CountInversionsInAnArray.java

public class CountInversionsInAnArray {

 /** This code counts Inversions of a given array using merge sort
 * Time Complexity : O(nlogn)
 *
 * @author lemidia
 */
 
 static public class MergeSort {
 
 public int divide(int data[], int p, int r){
 // inversions count var
 int inversion = 0;
 
 if(p<r){
 int q = (p+r)/2;
 inversion += divide(data, p, q);
 inversion += divide(data,q+1, r);
 inversion += merge(data, p, q, r);
 }
 
 return inversion;
 }
 
 public int merge(int data[], int p, int q, int r){
 int i = p; int j = q+1; int k = p;
 int temp[] = new int[data.length];
 
 // inversions count var
 int inversion = 0;
 
 while (i<=q && j<=r){
 if(data[i] <= data[j]){
 temp[k++] = data[i++];
 }else{
 // i<j이면서 data[i] > data[j]인 경우이므로 역전 관계이다.
 // left sub array와 right sub array는 이미 정렬이 완료된 상태이고 (여기서는 오름차순)
 // i<j이면서 data[i] > data[j] 이면 data[j]보다 큰 원소들이 left sub array에
 // (q+1)-i개 있게 된다.

 inversion += (q+1)-i;
 temp[k++] = data[j++];
 }
 }
 
 while (i<=q)
 temp[k++] = data[i++];
 while (j<=r)
 temp[k++] = data[j++];
 for(int l = p; l<=r; l++){
 data[l] = temp[l];
 }
 
 return inversion;
 }
 }
 
 public static void main(String[] args) {
 int limit = 10;
 int arr[] = new int[limit];

 // Sample Array is {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
 // The number of inversion Count will be 45
 // (9,8), (9,7) ... (2,0), (1,0) = 45 ea

 for(int i = limit-1; i>=0; --i)
 arr[i] = limit-i;

 MergeSort mg = new MergeSort();
 System.out.print("The number of inversion Element is : ");
 System.out.println(mg.divide(arr, 0, arr.length-1));

 // Output:
 // The number of inversion Element is : 45

 }
}