package InfinityJune21.DivideAndConquer;

import java.util.Arrays;

public class InversionCount {
    static int mergeAndCount(int arr[], int l, int m, int r) {
        int left[] = Arrays.copyOfRange(arr, l, m + 1);
        int right[] = Arrays.copyOfRange(arr, m + 1, r + 1);
        int i = 0, j = 0, k = l, swaps = 0;

        while(i < left.length && j < right.length) {
            if(left[i] <= right[j]) {
                arr[k++] = left[i++];
            }
            else {
                arr[k++] = right[j++];
                swaps = swaps + (m + 1) - (l + i);
            }
        }

        while(i < left.length) {
            arr[k++] = left[i++];
        }
        while(j < right.length) {
            arr[k++] = right[j++];
        }

        return swaps;
    }

    static int mergeSortAndCount(int arr[], int l, int r) {
        int count = 0;

        if(l < r) {
            int m = (l + r) / 2;
            count += mergeSortAndCount(arr, l, m);
            count += mergeSortAndCount(arr, m + 1, r);
            count += mergeAndCount(arr, l, m, r);
        }

        return count;
    }

    public static void main(String[] args) {
        int arr[] = {1, 20, 6, 4, 5};
        int numberOfInversions = mergeSortAndCount(arr, 0, arr.length - 1);
        System.out.println(numberOfInversions);
    }
}