Q24.java

public class Q24 {
    public static void main(String[] args) {
        int []a = new int[]{5,3 , 4 , 2 ,1 };
        System.out.println (inversion(a , 0 , a.length - 1));
        for (int x : a) {
            System.out.print(x + " ");
        }
    }

    private static int inversion(int[] a, int lo, int hi) {
        if(lo >= hi){
            return 0 ;
        }
        int mid = (lo + hi)/ 2 ;
        int c = 0;
        c+=inversion (a , lo , mid);
        c +=inversion (a , mid + 1, hi);
        c +=merge(a, lo , mid , hi);
        return c;
    }

    private static int merge(int[] a, int lo, int mid, int hi) {
        int size = hi - lo +1 ;
        int [] mix = new int[size];
        int i = lo;
        int k = 0;
        int count = 0;
        int j =mid + 1;
        while(i <= mid  && j <= hi){
            if(a[i] <= a[j ]){
                mix[k++] = a[i];
                i++;
            }
            else{
                mix[k++ ] = a[j ];
                count += mid - i + 1;
                j++;
            }
        }
        while(i <= mid){
            mix[k++ ] = a[i];
            i++;
        }
        while(hi>= j){
            mix[k++ ] = a[j];
            j++;
        }
        for (int m = 0; m < mix.length; m++) {
            a[lo + m] = mix[m];
        }
        return count;
    }
}