Count Inversions in an Array

Title: Count Inversions in an Array

In this guide, you’ll learn how to count inversions in an array of integers using Java. An inversion is a pair of indices i < j where arr[i] > arr[j], and the total inversion count is a classic measure of how far an array is from being sorted.

We’ll start with the brute-force idea, then build an efficient O(n log n) solution based on merge sort, trace it step by step, and work through examples, common mistakes, and edge cases so you’re ready to defend the approach in an interview.

Understanding the Problem

Given an array arr of n integers, an inversion is any pair of positions (i, j) with i < j and arr[i] > arr[j]. The goal is to count how many such pairs exist in the array.

A fully sorted array, ascending, has zero inversions, while a fully reverse-sorted array has the maximum possible number of inversions, n * (n - 1) / 2. The inversion count measures how unsorted a sequence is, and it shows up in related problems such as finding the minimum number of adjacent swaps needed to sort an array.

Approach

1. Compare every pair (i, j) with a nested loop and count the pairs where arr[i] > arr[j]; this brute-force approach runs in O(n^2).
2. To do better, adapt merge sort: split the array into two halves recursively until each half has one element.
3. While merging two already-sorted halves, every time an element from the right half is placed before an element from the left half, all remaining elements in the left half form an inversion with it.
4. Add (mid - i + 1) to the running inversion count each time this happens, where i is the current pointer into the left half and mid is its last index.
5. Recursively count inversions in the left half, the right half, and across the merge step, then sum all three counts.
6. Return the total count once the top-level merge completes; the array is now fully sorted as a side effect of the process.

Java Program

public class CountInversions {

    public static long countInversions(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int[] temp = new int[arr.length];
        return mergeSortAndCount(arr, temp, 0, arr.length - 1);
    }

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

    private static long mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = left;
        long inversions = 0;

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

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

        for (int x = left; x <= right; x++) {
            arr[x] = temp[x];
        }

        return inversions;
    }

    public static void main(String[] args) {
        int[] numbers = {8, 4, 2, 1};
        long totalInversions = countInversions(numbers);
        System.out.println("Inversion count: " + totalInversions);
    }
}

Explanation of the Program

• countInversions is the public entry point; it guards against a null or single-element array, neither of which can contain an inversion.
• mergeSortAndCount recursively splits the range [left, right] at mid, counting inversions in the left half, the right half, and the merge step, then returns their sum.
• mergeAndCount merges the two sorted halves [left, mid] and [mid + 1, right] back into order while counting cross-half inversions.
• Whenever arr[j] from the right half is smaller than arr[i] from the left half, every element from arr[i] through arr[mid] is greater than arr[j], so (mid - i + 1) inversions are added at once.
• The temp array holds the merged result for the current range, which is copied back into arr so that outer recursive calls see a sorted subrange.
• The count is returned as a long because the maximum possible inversion count, n * (n - 1) / 2, can exceed Integer.MAX_VALUE for large values of n.

Step-by-Step Trace

Consider merging two already-sorted halves, left = [2, 5, 8] and right = [1, 3, 9], into one sorted sequence while counting inversions. The target output is the merged array [1, 2, 3, 5, 8, 9] with an inversion count of 5.

At the end of each comparison, inversions holds the total number of left-half elements that were still unplaced the moment a smaller right-half element jumped ahead of them.

Examples

Example 1: Already Sorted Array

An already sorted array has no element appearing before a smaller one, so the inversion count is zero.

int[] arr = {1, 2, 3, 4, 5};
System.out.println(countInversions(arr));
// Output: 0

Example 2: Reverse Sorted Array

A fully reverse sorted array produces the maximum possible inversion count, n * (n - 1) / 2.

int[] arr = {5, 4, 3, 2, 1};
System.out.println(countInversions(arr));
// Output: 10

Example 3: Mixed Order Array

Most real inputs fall between those two extremes; here only some pairs are out of order.

int[] arr = {2, 3, 8, 6, 1};
System.out.println(countInversions(arr));
// Output: 5

Common Mistakes to Avoid

These are the mistakes that most often slip into a merge-sort based inversion counter.

• Using int for the count – overflows for large arrays because the maximum inversion count, n * (n - 1) / 2, exceeds Integer.MAX_VALUE once n passes roughly 65,536. Use long for the running count.
• Forgetting to copy temp back into arr – leaves the subrange unsorted, so outer recursive calls compare against stale data and undercount inversions. Always copy temp[left..right] back into arr after each merge.
• Reaching for a brute-force double loop on large input – an O(n^2) scan times out once n reaches a few hundred thousand elements. Switch to the merge-sort based counter for O(n log n).
• Miscomputing (mid – i + 1) – an off-by-one here silently inflates or shrinks the count because it misrepresents how many left-half elements are still unplaced. Recheck that i and mid refer to the current merge range, not the original array bounds.
• Assuming the input array keeps its original order – countInversions sorts arr in place as a side effect, so callers who need the original order back get silently reordered data. Pass a cloned array if the caller must not see the mutation.

Edge Cases to Test

Walk through these boundary inputs before calling the solution complete.

• Empty array
• Single-element array
• Null array reference
• Already sorted array
• Reverse sorted array (maximum inversions)
• Array with all identical elements
• Array with duplicate values mixed among unique ones
• Large array where the count can exceed Integer.MAX_VALUE

Additional Considerations

The brute-force double loop runs in O(n^2) time with O(1) extra space, which is fine for small arrays but far too slow once n grows past a few thousand elements.

The merge-sort based approach runs in O(n log n) time and uses O(n) extra space for the temp array, since counting inversions is piggybacked on the merge step at no extra asymptotic cost over sorting alone.

Because countInversions sorts arr in place as a side effect, callers who need to preserve the original order should pass a cloned array, and the count itself should always be stored as a long to avoid overflow on large inputs.

Interview Follow-up Questions

Interviewers often extend this problem to probe how well you understand the underlying technique.

• What if you only need to know whether the array has zero inversions? – a single O(n) pass checking arr[i] <= arr[i + 1] for every adjacent pair answers that without running the full counter.
• What if duplicate values must not be counted as inversions? – nothing changes; keeping the merge comparison as arr[i] <= arr[j] already treats equal elements as non-inverted.
• What if you need the inversion count without permanently reordering the original array? – clone the array before calling countInversions, or carry the original indices alongside each value and count inversions with a Binary Indexed Tree over compressed ranks instead of sorting in place.
• What if values arrive one at a time as a stream and you must report the running inversion count after every insertion? – maintain a Binary Indexed Tree keyed by rank; each insertion queries how many already-inserted values are greater than the new one in O(log n), giving O(n log n) total with coordinate compression.
• What if the array has billions of elements and does not fit in memory? – use external merge sort over on-disk chunks; cross-chunk inversions fall out of the standard k-way merge step the same way they do for an in-memory array.

Conclusion

Counting inversions is a great example of extending a classic algorithm, merge sort, to answer a question beyond sorting. The brute-force approach is easy to reason about, but the merge-sort based technique gets you to O(n log n) by counting pairs for free while merging.

Try adapting countInversions to return the actual out-of-order pairs, or to work on a List<Integer> instead of a primitive array, to deepen your understanding. You can learn more about array-based algorithms in our Arrays category.