Count Inversions in an Array

Given an array, count its inversions: pairs of indices i < j with a[i] > a[j]. A sorted array has 0 inversions, and a reversed array has the maximum, n(n - 1) / 2.

Example

Text

Input:  [2, 4, 1, 3, 5]    Output: 3   ((2, 1), (4, 1), (4, 3))
Input:  [5, 4, 3, 2, 1]    Output: 10

Brute force: check every pair

Java

public class Main {
    static long countInversions(int[] a) {
        long count = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] > a[j]) {
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countInversions(new int[] {2, 4, 1, 3, 5}) + " " + countInversions(new int[] {5, 4, 3, 2, 1}));
    }
}

Output

3 10

Time: O(n²). Space: O(1).

Optimal: count while merge sorting

Split the array in half. Every inversion is inside the left half, inside the right half, or across the halves (the larger value on the left). Recursion counts the first two kinds and sorts both halves. The cross inversions are counted during the merge:

When the merge takes right[j] because it is smaller than left[i], it is also smaller than every remaining element left[i..], because the left half is sorted. That is left.length - i inversions in one step.

Text

left = [2, 4]   right = [1, 3, 5]
take 1 (from right): 2 and 4 remain on the left  -> +2
take 2 (from left)
take 3 (from right): 4 remains on the left       -> +1
take 4, take 5                                   -> total 3

Java

import java.util.Arrays;

public class Main {
    // Sorts a[from, to) and returns the number of inversions inside it.
    static long sortCount(int[] a, int from, int to) {
        if (to - from < 2) {
            return 0;
        }
        int mid = from + (to - from) / 2;
        long count = sortCount(a, from, mid) + sortCount(a, mid, to);

        int[] left = Arrays.copyOfRange(a, from, mid);
        int[] right = Arrays.copyOfRange(a, mid, to);
        int i = 0;
        int j = 0;
        for (int slot = from; slot < to; slot++) {
            if (j == right.length || (i < left.length && left[i] <= right[j])) {
                a[slot] = left[i++];
            } else {
                a[slot] = right[j++];
                count += left.length - i; // right[j] is smaller than all of left[i..]
            }
        }
        return count;
    }

    static long countInversions(int[] a) {
        int[] copy = a.clone();
        return sortCount(copy, 0, copy.length);
    }

    public static void main(String[] args) {
        System.out.println(countInversions(new int[] {2, 4, 1, 3, 5}) + " " + countInversions(new int[] {5, 4, 3, 2, 1}));
        System.out.println(countInversions(new int[] {1, 1, 1}) + " " + countInversions(new int[] {}));
    }
}

Output

3 10
0 0

Time: O(n log n). Space: O(n) for the merge buffers (Arrays.copyOfRange copies each half into a new array).

Taking from the left on ties (<=) matters: equal values are not inversions, so an element from the right half must not be counted against an equal element on the left.

Edge cases

Duplicates: equal pairs are not counted.
Large arrays: the count can reach about n² / 2, which overflows int (maximum 2,147,483,647) for n above about 65,000. The result is a long.
Keeping the input: countInversions sorts a copy made with clone(), so the caller's array is unchanged.