Count Inversions in an Array in Java

1. Overview

In this tutorial, we’ll explore the problem of counting inversions in an array, a concept used in computer science to measure how far an array is from being sorted.

We’ll start by defining an inversion and providing examples to illustrate the concept. From there, we’ll dive into two main approaches to solving the problem.

First, we’ll implement a brute-force method, which checks each possible pair of elements to find inversions. Then, we’ll move on to a more efficient divide-and-conquer technique that leverages a modified merge sort algorithm to reduce the number of comparisons significantly.

2. What Is an Inversion in an Array?

An inversion in an array is simply a situation where two elements are out of order. Specifically, an inversion occurs if an element at a lower index is larger than one at a higher index. In other words, if we have an array A, an inversion is any pair of indices (i, j) where:

• i < j
• A[i] > A[j]

In a sorted array we have no inversions because every element is properly placed. But in an unsorted array, the number of inversions tells us how “disordered” the array is. The more inversions, the more steps we need to take to sort the array by swapping adjacent elements.

2.1. Example

Let’s look at a simple example. Suppose we have an array:

int[] array = {3, 1, 2};

3. Brute-Force Approach

The brute-force approach to counting inversions is straightforward. We go through each possible pair of elements in the array and check if they form an inversion. This approach is simple to understand and implement, but it has a time complexity of O(n^2), which makes it inefficient for larger arrays.

In this approach, we iterate through each element in the array with a nested loop. For each pair (i, j), where i < j, we check if A[i] > A[j]. If it is, we’ve found an inversion and increase the count:

@Test
void givenArray_whenCountingInversions_thenReturnCorrectCount() {
    int[] input = {3, 1, 2};
    int expectedInversions = 2;

    int actualInversions = countInversionsBruteForce(input);

    assertEquals(expectedInversions, actualInversions);
}

int countInversionsBruteForce(int[] array) {
    int inversionCount = 0;
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = i + 1; j < array.length; j++) {
            if (array[i] > array[j]) {
                inversionCount++;
            }
        }
    }
    return inversionCount;
}

This brute-force solution works well for small arrays, but as the size of the array increases, its inefficiency becomes evident.

4. Optimized Approach: Divide-And-Conquer

The divide-and-conquer approach significantly improves the efficiency of counting inversions by leveraging the principles of merge sort. Instead of checking each pair individually, we recursively split the array into two halves until each half has one element (or no elements). As we merge these halves back together in sorted order, we count the inversions where elements in the left half are greater than those in the right half:

@Test
void givenArray_whenCountingInversionsWithOptimizedMethod_thenReturnCorrectCount() {
    int[] inputArray = {3, 1, 2};
    int expectedInversions = 2;

    int actualInversions = countInversionsDivideAndConquer(inputArray);

    assertEquals(expectedInversions, actualInversions);
}

Next, we define the countInversionsDivideAndConquer() method. This method serves as the algorithm entry point. It checks if the input array is valid and delegates the inversion counting logic to another method:

int countInversionsDivideAndConquer(int[] array) {
    if (array == null || array.length <= 1) {
        return 0;
    }
    return mergeSortAndCount(array, 0, array.length - 1);
}

The core logic of the algorithm resides in the mergeSortAndCount() method. This method divides the array into two halves, processes each half recursively to count the inversions within them, and then merges them back together in sorted order while tallying any inversions that occur between the two halves:

int mergeSortAndCount(int[] array, int left, int right) {
    if (left >= right) {
        return 0;
    }

    int mid = left + (right - left) / 2;
    int inversions = mergeSortAndCount(array, left, mid) + mergeSortAndCount(array, mid + 1, right);

    inversions += mergeAndCount(array, left, mid, right);
    return inversions;
}

Finally, the mergeAndCount() method handles the merging process. It merges two sorted halves of the array and simultaneously counts cross-inversions (when an element in the left half is greater than one in the right half).

The first part of the mergeAndCount() method creates temporary arrays to hold the left and right halves of the array being merged:

int[] leftArray = new int[mid - left + 1];
int[] rightArray = new int[right - mid];

System.arraycopy(array, left, leftArray, 0, mid - left + 1);
System.arraycopy(array, mid + 1, rightArray, 0, right - mid);

System.arraycopy() efficiently copies elements from the original array into the temporary arrays.

After creating temporary arrays, we initialize pointers for traversal and a variable to keep track of inversions. In the next part, we merge the two halves while counting cross-inversions:

int i = 0, j = 0, k = left, inversions = 0;

while (i < leftArray.length && j < rightArray.length) {
    if (leftArray[i] <= rightArray[j]) {
        array[k++] = leftArray[i++];
    } else {
        array[k++] = rightArray[j++];
        inversions += leftArray.length - i;
    }
}

We add leftArray.length – i to the inversions counter, as these are all the elements causing inversions.

After processing all elements in one array, there may still be elements left in the other array. These elements are copied into the original array:

while (i < leftArray.length) {
    array[k++] = leftArray[i++];
}

while (j < rightArray.length) {
    array[k++] = rightArray[j++];
}

return inversions;

This optimization enables the algorithm to achieve the improved O(n * log⁡ n) time complexity.

5. Comparison

When comparing the brute-force and divide-and-conquer approaches, the key difference lies in their efficiency. The brute-force method iterates through all possible pairs in the array, checking each for inversions, which results in a time complexity of O(n^2). This makes it inefficient for large arrays, as the number of operations grows rapidly with the array size.

In contrast, the divide-and-conquer approach leverages the merge sort algorithm to efficiently count inversions while sorting the array. By dividing the array into halves and counting inversions both within and across these halves, this method achieves a time complexity of O(n * log n). This significant improvement makes it far more suitable for larger datasets, as it scales efficiently with increased input sizes.

6. Conclusion

In this article, we explored how to count inversions in an array. We started with a clear definition and a practical example to explain inversions. Then, we examined two methods to solve the problem. The first is a simple brute-force approach. The second is a more efficient divide-and-conquer method using merge sort. The brute-force method is easy to implement but inefficient for large arrays. In contrast, the divide-and-conquer approach uses recursion to reduce time complexity greatly.