Counting Inversions — 64-bit Overflow at 50K Items

def count_inversions(arr: list) -> tuple[list, int]:
    """Returns (sorted_array, inversion_count)"""
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left,  left_inv  = count_inversions(arr[:mid])
    right, right_inv = count_inversions(arr[mid:])
    merged, split_inv = merge_count(left, right)
    return merged, left_inv + right_inv + split_inv

def merge_count(left: list, right: list) -> tuple[list, int]:
    merged, inversions = [], 0
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            # left[i..] all form inversions with right[j]
            inversions += len(left) - i
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, inversions

_, count = count_inversions([2, 4, 1, 3, 5])
print(f'Inversions: {count}')  # 3

_, count = count_inversions([5, 4, 3, 2, 1])
print(f'Inversions in reverse: {count}')  # 10

def min_swaps_to_sort(arr):
    _, count = count_inversions(arr)
    return count

print(min_swaps_to_sort([3, 1, 2]))  # 2 swaps: [3,1,2]→[1,3,2]→[1,2,3]

def iterative_count_inversions(arr: list) -> int:
    """Iterative bottom-up merge sort counting inversions."""
    n = len(arr)
    temp = [0] * n
    inversions = 0
    size = 1
    while size < n:
        for left_start in range(0, n, 2 * size):
            mid = min(left_start + size, n)
            right_end = min(left_start + 2 * size, n)
            i = left_start
            j = mid
            k = left_start
            while i < mid and j < right_end:
                if arr[i] <= arr[j]:
                    temp[k] = arr[i]
                    i += 1
                else:
                    inversions += mid - i
                    temp[k] = arr[j]
                    j += 1
                k += 1
            while i < mid:
                temp[k] = arr[i]
                i += 1
                k += 1
            while j < right_end:
                temp[k] = arr[j]
                j += 1
                k += 1
        arr[:] = temp
        size *= 2
    return inversions

data = list(range(100000, 0, -1))
inv = iterative_count_inversions(data)
print(f'Inversions in 100k reverse-sorted: {inv}')

def kendall_tau(ranking_a: list, ranking_b: list) -> float:
    """Compute Kendall tau correlation between two rankings."""
    n = len(ranking_a)
    # Map each item in ranking_a to its position
    pos = {item: idx for idx, item in enumerate(ranking_a)}
    # Transform ranking_b into an array of positions relative to a
    b_positions = [pos[item] for item in ranking_b]
    # Number of discordant pairs = inversion count of b_positions
    _, inversions = count_inversions(b_positions)
    # Total pairs
    total_pairs = n * (n - 1) // 2
    # Kendall tau = (concordant - discordant) / total = 1 - 2*(inversions / total)
    tau = 1 - (2 * inversions) / total_pairs
    return tau

# Example: same ranking
print(kendall_tau([1,2,3,4,5], [1,2,3,4,5]))  # 1.0
# Reverse ranking
print(kendall_tau([1,2,3,4,5], [5,4,3,2,1]))  # -1.0
# Slightly different
print(kendall_tau([1,2,3,4,5], [2,1,3,4,5]))  # 0.8

// io.thecodeforge — dsa tutorial

public class InversionBruteForce {
    public static int countInversions(int[] data) {
        int count = 0;
        int n = data.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (data[i] > data[j]) {
                    count++;
                }
            }
        }
        return count;
    }

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

// io.thecodeforge — dsa tutorial

public class InversionMergeSort {
    public static long countInversionsAndMerge(int[] data) {
        int[] temp = new int[data.length];
        return mergeSortAndCount(data, temp, 0, data.length - 1);
    }

    private static long mergeSortAndCount(int[] data, int[] temp, int left, int right) {
        if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        long count = mergeSortAndCount(data, temp, left, mid);
        count += mergeSortAndCount(data, temp, mid + 1, right);
        count += merge(data, temp, left, mid, right);
        return count;
    }

    private static long merge(int[] data, int[] temp, int left, int mid, int right) {
        int i = left, j = mid + 1, k = left;
        long invCount = 0;
        while (i <= mid && j <= right) {
            if (data[i] <= data[j]) {
                temp[k++] = data[i++];
            } else {
                // All elements from i to mid are > data[j]
                invCount += (mid - i + 1);
                temp[k++] = data[j++];
            }
        }
        while (i <= mid) temp[k++] = data[i++];
        while (j <= right) temp[k++] = data[j++];
        System.arraycopy(temp, left, data, left, right - left + 1);
        return invCount;
    }

    public static void main(String[] args) {
        int[] arr = {4, 3, 2, 1};
        System.out.println("Merge sort inversions: " + countInversionsAndMerge(arr));
    }
}