Count Inversions using Merge Sort

Title: Count Inversions using Merge Sort

In this guide, you’ll learn how to count the number of inversions in an array using a modified merge sort. An inversion is a pair of elements that are out of their sorted order, and counting them efficiently is a classic interview question that tests whether you understand divide and conquer beyond simple sorting. We’ll build the algorithm step by step, trace it on a concrete example, and walk through the edge cases an interviewer expects you to raise.

Understanding the Problem

Given an array of integers, an inversion is any pair of indices i and j where i < j but arr[i] > arr[j]. In other words, the element at the earlier position is larger than the element at the later position, which is the opposite of what a sorted array would look like.

A naive approach checks every pair with two nested loops, which costs O(n^2) time. For large arrays this is too slow. Merge sort already breaks the array into halves and merges them back together in sorted order, and that merge step happens to be the perfect place to count inversions for free, without adding extra passes over the data.

Approach: Counting Inversions with Merge Sort

1. If the array has fewer than two elements, there are no inversions, so return 0 immediately.
2. Split the array into a left half and a right half around the midpoint.
3. Recursively count the inversions inside the left half.
4. Recursively count the inversions inside the right half.
5. Merge the two sorted halves back together, and while merging, count the inversions that occur between an element from the left half and an element from the right half.
6. Whenever an element from the right half is placed into the result before all remaining elements of the left half, add the count of those remaining left elements to the inversion total, since each one forms an inversion with that right-half element.
7. Add the inversions found in the left half, the right half, and the merge step to get the total inversion count for the current range.
8. Return the total once the top-level call across the full array finishes.

Java Program

The program below implements countInversions using a merge sort that returns a long running total instead of just sorting the array in place.

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 = {2, 4, 1, 3, 5};
        long inversionCount = countInversions(numbers);
        System.out.println("Inversion count: " + inversionCount);
    }
}

Explanation of the Program

The public method countInversions handles the trivial cases and allocates a single temp array once, which mergeSortAndCount reuses across every recursive call.

• mergeSortAndCount splits the range into two halves around mid and recurses on both halves before merging, exactly like a standard merge sort.
• mergeAndCount walks the two halves with pointers i and j, copying the smaller of arr[i] and arr[j] into temp at position k.
• When arr[j] is smaller and gets copied first, every remaining element in the left half from i to mid forms an inversion with arr[j], so mid - i + 1 is added to the running count.
• After one pointer reaches the end of its half, the leftover elements from the other half are copied over without adding to the count, since they are already in order relative to each other.
• The final loop copies temp[left..right] back into arr so the array is actually sorted by the time the recursion unwinds.

Step-by-Step Trace

Consider merging two already-sorted halves, left = [1, 3, 8] and right = [2, 4, 6], which together form the array [1, 3, 8, 2, 4, 6] with mid pointing at index 2. The merge below should finish with the sorted array [1, 2, 3, 4, 6, 8] and an inversion count of 4.

At the end of each step, total holds every cross-inversion discovered so far between the still-unmerged elements of the left half and the elements of the right half already copied into the array.

Examples

The examples below show how the inversion count behaves on different input shapes.

Example 1: Already Sorted Array

A sorted array has no inversions at all, since every earlier element is already less than or equal to every later one.

int[] numbers = {1, 2, 3, 4, 5};
long result = CountInversions.countInversions(numbers);
// result is 0

Example 2: Reverse-Sorted Array

A fully reverse-sorted array is the worst case, where every pair of elements forms an inversion.

int[] numbers = {5, 4, 3, 2, 1};
long result = CountInversions.countInversions(numbers);
// result is 10

Example 3: Array with Duplicate Elements

Equal elements are never counted as inversions, which matters once the array has repeated values.

int[] numbers = {3, 3, 1, 2};
long result = CountInversions.countInversions(numbers);
// result is 4

Common Mistakes to Avoid

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

• Forgetting to copy the merge back into arr – the array still looks unsorted after the call returns even though the inversion count is correct, because temp holds the merged values but arr was never updated. Always copy temp[left..right] back into arr at the end of mergeAndCount.
• Wrong comparison operator in the merge – using arr[i] < arr[j] instead of arr[i] <= arr[j] makes equal elements swap unnecessarily, inflating the count on arrays like [3, 3, 1, 2]. Use <= so equal elements are never counted as inversions.
• Counting from the wrong half’s remaining size – adding right - j + 1 instead of mid - i + 1 gives the wrong inversion total, because the contribution should always be the number of elements still remaining in the left half at that moment.
• Reallocating temp on every recursive call – the final answer is still correct, but allocating a new array inside mergeSortAndCount pushes the running time toward O(n^2 log n). Allocate temp once in countInversions and reuse it across all calls.
• Returning an int from countInversions – silently overflows on large reverse-sorted arrays, since the count can approach n * (n - 1) / 2. Use long for both the accumulator and the return type.

Edge Cases to Test

Walk through these input shapes out loud before an interviewer has to ask.

• Empty array
• Single-element array
• Already sorted array (zero inversions)
• Fully reverse-sorted array (maximum inversions)
• Array with duplicate elements
• Array with all identical elements
• Very large array (overflow risk for the inversion count)
• Null array reference

Additional Considerations

The algorithm’s time complexity is O(n log n), the same as ordinary merge sort, because the inversion counting adds only constant work per merge step rather than any extra passes over the array.

Space complexity is O(n) for the temp array, plus O(log n) for the recursion stack, since the array is halved at every recursive call.

The inversion count for a fully reverse-sorted array of size n is n * (n - 1) / 2, which exceeds the range of a 32-bit int once n passes roughly 92,682. That is why the method signature uses long rather than int.

Interview Follow-up Questions

Once you can explain the base algorithm cleanly, expect an interviewer to push further with questions like these.

• What if you only need to know whether any inversion exists, not the exact count? – short-circuit the merge step and return true the first time arr[i] > arr[j], skipping the rest of the array.
• What if the array must be sorted without allocating the extra temp array? – use an in-place merge, such as rotating the overlapping block during each merge step, trading extra time for the saved O(n) space.
• What if the input is too large to fit in memory and arrives as a stream? – use an external merge sort that writes sorted runs to disk, then count the cross-run inversions during the k-way merge phase instead of an in-memory two-way merge.
• What if the inversion count must stay current as elements are appended one at a time? – maintain a Fenwick tree (binary indexed tree) over the compressed value ranks, and on each insertion add the count of already-inserted elements greater than the new one, giving O(log n) per update instead of re-running the whole algorithm.

Conclusion

Counting inversions with merge sort is a great example of getting a second useful result almost for free from an algorithm you already know. The same divide and conquer structure that sorts the array also tells you exactly how far it is from being sorted.

Try adapting the code above to count inversions in a linked list, or to find the minimum number of adjacent swaps needed to sort an array, which is the same quantity viewed from a different angle. You can learn more about array-based algorithms like this one in the Arrays category on Daily Java Concept.