Inversion count in an array Merge Sort

 avatar
unknown
java
a year ago
1.4 kB
6
Indexable
public class DivideandConquer_inversion_count {
    static int count = 0;
    public static int[] countInversion(int[] arr,int si,int ei){
        if(si == ei){
            int[] ba = new int[1];
            ba[0] = arr[si];
            return ba;
        }

        int mid = si+(ei-si)/2;
        int[] left = countInversion(arr,si,mid);
        int[] right = countInversion(arr,mid+1,ei);

        int[] res = mergeTwoSortedArrays(left,right);
        return res;
    }

    public static int[] mergeTwoSortedArrays(int[] left, int[] right){
       int n = left.length;
       int m = right.length;

       int[] res = new int[n+m];

       int i=0;
       int j=0;
       int k=0;

       while (i<n && j<m){
           if(left[i] < right[j]){
               res[k] = left[i];
               i++;
           }else {
               res[k] = right[j];
               count += (n-i);
               j++;
           }
           k++;
       }
       while (i<n){
           res[k] = left[i];
           i++;
           k++;
       }
       while (j<m){
           res[k] = right[j];
           j++;
           k++;
       }
       return res;
    }
    public static void main(String[] args) {
        int[] arr = {4,1,7,2,9,5};
        int[] res =  countInversion(arr,0,5);

        System.out.println(count);
    }
}
Editor is loading...
Leave a Comment