1. Introduction

An inversion in an array a[] is a pair (a[i], a[j]) such that i < j and a[i] > a[j]. The Inversion Count of an array indicates how far (or close) the array is from being sorted. If the array is already sorted, then the inversion count is 0. This metric is often used in computer science, especially in the domain of algorithms, to measure the complexity or efficiency of a sorting process.

2. Program Steps

1. Use a divide-and-conquer strategy similar to merge sort.

2. Divide the array into two halves.

3. Recursively count the inversions in both halves and then count inversions between the two halves.

4. Merge the two halves while counting the inversions.

3. Code Program

public class InversionCount {

    // Merges two sorted subarrays and returns inversion count in the arrays.
    private static int mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left;
        int j = mid;
        int k = left;
        int inv_count = 0;

        while ((i <= mid - 1) && (j <= right)) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
                inv_count = inv_count + (mid - i);
            }
        }

        while (i <= mid - 1) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];

        for (i = left; i <= right; i++) arr[i] = temp[i];

        return inv_count;
    }

    private static int _mergeSort(int[] arr, int[] temp, int left, int right) {
        int mid, inv_count = 0;
        if (right > left) {
            mid = (right + left) / 2;

            inv_count = _mergeSort(arr, temp, left, mid);
            inv_count += _mergeSort(arr, temp, mid + 1, right);

            inv_count += mergeAndCount(arr, temp, left, mid + 1, right);
        }
        return inv_count;
    }

    public static int countInversions(int[] arr) {
        int[] temp = new int[arr.length];
        return _mergeSort(arr, temp, 0, arr.length - 1);
    }

    public static void main(String[] args) {
        int[] arr = {8, 4, 2, 1};
        System.out.println("Number of inversions are: " + countInversions(arr));
    }
}

Output:

Number of inversions are: 6

4. Step By Step Explanation

1. The main function to count inversions in the array is countInversions(). This function uses the auxiliary function _mergeSort(), which is a variation of the standard merge sort algorithm.

2. _mergeSort() divides the array into halves and finds the inversion count in the two halves using recursive calls.

3. The function mergeAndCount() is used to merge two halves and count inversions between two halves.

4. The inversions between two halves are essentially the values in the left half which are greater than values in the right half. The mergeAndCount() function uses this logic to add to the count while it merges the two halves.

5. The final count is the sum of inversions in the left half, right half, and those between the two halves.