DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Count Inversion using merge sort

Count Inversion

class Solution {
    static int inversionCount(int arr[]) {
        // Code Here
        return merge(0, arr.length-1, arr);

    }
    public static int merge(int i , int j, int nums[]){
    int count =0;
    if(i<j){
        int m = (i+j)/2;
        count+=merge(i,m,nums);
        count+=merge(m+1,j,nums);
        count+=sort(i,m,j,nums);
    }
    return count;

    }
    public static int sort(int i , int k, int j, int arr[]){
        int count =0;
        int a[]  =new int[k-i+1];
        int b[] = new int[j-k];//j-(k+1) + 1

        for(int p=0;p<a.length;p++){
            a[p] = arr[p+i];
        }
        for(int q = 0;q<b.length;q++){
            b[q] = arr[q+k+1];
        }


        int p = 0;
        int q = 0;
        int r = i;
        while(p<a.length && q<b.length){
            if(a[p]<=b[q]){
                arr[r] = a[p];
                p++;
            }
            else{
                arr[r] = b[q];
                count+=a.length-p;
                q++;
            }
            r++;
        }

        while(p<a.length){
            arr[r] = a[p];
            r++;
            p++;
        }
        while(q<b.length){
            arr[r] = b[q];
            r++;
            q++;
        }

        return count;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)