Count Inversions in an Array

Problem Statement

An inversion is a pair (i, j) with i < j but arr[i] > arr[j]. Count the total number of inversions, which measures how far the array is from sorted.

Example

Input:  [8, 4, 2, 1]
Output: 6  (every pair is out of order)

Approach

Use a modified merge sort. During the merge of two sorted halves, when an element from the right half is placed before remaining elements of the left half, every one of those remaining left elements forms an inversion with it — add their count. Summing across all merges gives the total in O(n log n).

Complexity

• Time: O(n log n)
• Space: O(n)

Solution Code

Python

def count_inversions(arr):
    def sort_count(a):
        if len(a) <= 1:
            return a, 0
        mid = len(a) // 2
        left, cl = sort_count(a[:mid])
        right, cr = sort_count(a[mid:])
        merged, cm = merge_count(left, right)
        return merged, cl + cr + cm
    def merge_count(a, b):
        res, i, j, inv = [], 0, 0, 0
        while i < len(a) and j < len(b):
            if a[i] <= b[j]:
                res.append(a[i]); i += 1
            else:
                res.append(b[j]); j += 1
                inv += len(a) - i
        res.extend(a[i:]); res.extend(b[j:])
        return res, inv
    return sort_count(arr)[1]

Java

long countInversions(int[] arr) {
    return sortCount(arr, 0, arr.length - 1, new int[arr.length]);
}
long sortCount(int[] a, int lo, int hi, int[] tmp) {
    if (lo >= hi) return 0;
    int mid = (lo + hi) / 2;
    long inv = sortCount(a, lo, mid, tmp) + sortCount(a, mid + 1, hi, tmp);
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else { tmp[k++] = a[j++]; inv += mid - i + 1; }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi) tmp[k++] = a[j++];
    for (int x = lo; x <= hi; x++) a[x] = tmp[x];
    return inv;
}

C++

long long sortCount(vector<int>& a, int lo, int hi, vector<int>& tmp) {
    if (lo >= hi) return 0;
    int mid = (lo + hi) / 2;
    long long inv = sortCount(a, lo, mid, tmp) + sortCount(a, mid + 1, hi, tmp);
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else { tmp[k++] = a[j++]; inv += mid - i + 1; }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi) tmp[k++] = a[j++];
    for (int x = lo; x <= hi; x++) a[x] = tmp[x];
    return inv;
}
long long countInversions(vector<int>& arr) {
    vector<int> tmp(arr.size());
    return sortCount(arr, 0, (int)arr.size() - 1, tmp);
}

Key Takeaways

• Inversions are counted for free during the merge step.
• Use a 64-bit counter — inversions can reach ~n^2/2.
• Reference: CLRS, Problem 2-4; GeeksforGeeks, "Count Inversions".