CountingInversions.java

package com.thealgorithms.divideandconquer;

/**
 * A utility class for counting the number of inversions in an array.
 * <p>
 * An inversion is a pair (i, j) such that i < j and arr[i] > arr[j].
 * This class implements a divide-and-conquer approach, similar to merge sort,
 * to count the number of inversions efficiently.
 * <p>
 * Time Complexity: O(n log n)
 * Space Complexity: O(n) (due to temporary arrays during merge step)
 *
 * <p>Applications:
 * - Used in algorithms related to sorting and permutation analysis.
 * - Helps in determining how far an array is from being sorted.
 * - Applicable in bioinformatics and signal processing.
 *
 * <p>This class cannot be instantiated, as it is intended to provide
 * only static utility methods.
 *
 * @author Hardvan
 */
public final class CountingInversions {
    private CountingInversions() {
    }

    /**
     * Counts the number of inversions in the given array.
     *
     * @param arr The input array of integers.
     * @return The total number of inversions in the array.
     */
    public static int countInversions(int[] arr) {
        return mergeSortAndCount(arr, 0, arr.length - 1);
    }

    /**
     * Recursively divides the array into two halves, sorts them, and counts
     * the number of inversions. Uses a modified merge sort approach.
     *
     * @param arr  The input array.
     * @param left The starting index of the current segment.
     * @param right The ending index of the current segment.
     * @return The number of inversions within the segment [left, right].
     */
    private static int mergeSortAndCount(int[] arr, int left, int right) {
        if (left >= right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int inversions = 0;

        inversions += mergeSortAndCount(arr, left, mid);
        inversions += mergeSortAndCount(arr, mid + 1, right);
        inversions += mergeAndCount(arr, left, mid, right);
        return inversions;
    }

    /**
     * Merges two sorted subarrays and counts the cross-inversions between them.
     * A cross-inversion occurs when an element from the right subarray is
     * smaller than an element from the left subarray.
     *
     * @param arr The input array.
     * @param left The starting index of the first subarray.
     * @param mid The ending index of the first subarray and midpoint of the segment.
     * @param right The ending index of the second subarray.
     * @return The number of cross-inversions between the two subarrays.
     */
    private static int mergeAndCount(int[] arr, int left, int mid, int right) {
        int[] leftArr = new int[mid - left + 1];
        int[] rightArr = new int[right - mid];

        System.arraycopy(arr, left, leftArr, 0, mid - left + 1);
        System.arraycopy(arr, mid + 1, rightArr, 0, right - mid);

        int i = 0;
        int j = 0;
        int k = left;
        int inversions = 0;

        while (i < leftArr.length && j < rightArr.length) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
                inversions += mid + 1 - left - i;
            }
        }

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

        return inversions;
    }
}