Count Inversions in an Array using Merge Sort (with code)

In computer science, understanding the concept of inversions in an array is crucial. Inversions provide insights into the order and arrangement of elements within an array and have significant applications in various algorithms. In this article, we will learn what is inversion count in an array and how to count inversions in an array.

What is Inversion in an Array?

Inversions in an array occur when two elements are out of their natural order. In simple terms, it implies that the higher-valued element appears before the lower-valued element in the array, violating the expected ordering.

To formally define inversions in an array, we can use the concept of indices. Consider an array A of length n. If we have indices i and j such that 0 ≤ i < j < n, and A[i] > A[j], then we have an inversion (A[i], A[j]).

For example, let's consider the array [2, 4, 1, 3, 5]. The inversions in this array are (2, 1) and (4, 1) since the elements 2 and 4 appear before 1 in the array, violating the ascending order.

Counting Inversions in an Array

Counting inversions in an array refers to the process of determining the total number of inversions present within the elements of the array.

The counting inversions problem is not only interesting in its own right but also has various applications in algorithmic analysis and problem-solving. It provides insights into the degree of disorder or "sortedness" of an array and can serve as a basis for implementing sorting algorithms or detecting similarities and differences between sequences.

There are multiple algorithms to count inversions in an array. We'll explore two popular approaches:

Brute Force Approach

The brute force approach involves comparing every pair of elements in the array to identify inversions. This approach has a time complexity of O(n^2) since it requires examining all pairs. While simple to implement, it is not efficient for large arrays.

Here's an example of counting inversions in an array using the brute force approach in C++:

#include<iostream>
#include<vector> 

using namespace std;

int countInversionsBruteForce(const vector<int>& arr) {
    int n = arr.size();
    int inversions = 0;

    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] > arr[j]) {
                inversions++;
            }
        }
    }

    return inversions;
}

int main() {
    vector<int> arr = {5, 2, 8, 1, 9};
    int inversionCount = countInversionsBruteForce(arr);
    cout << "Number of inversions: " << inversionCount << endl;

    return 0;
} 

Output:

Number of inversions: 4

In this code, the function countInversionsBruteForce takes an array as input and counts the number of inversions present in the array using the brute force approach.

The outer loop iterates over each element of the array from the first element to the second-to-last element. The inner loop then compares the current element with all the elements that follow it, counting the inversions whenever the current element is greater than any subsequent element.

We provide an example array [5,2,8,1,9] and print the number of inversions using the function.

The time complexity of the brute force approach for counting inversions is O(n^2), where n is the length of the array. The space complexity is O(1).

Divide and Conquer Approach (Modified Merge Sort)

The divide and conquer approach, based on the concept of modified merge sort, provides an efficient solution to count inversions. This approach has a time complexity of O(n log n) and is widely used.

The algorithm involves recursively dividing the array into subarrays until they consist of single elements. During the merge step, while combining the sorted subarrays, the inversions are counted by tracking elements that are out of order.

The inversion count is the sum of inversions in the left subarray, right subarray, and the inversions that occur during the merging process.

Here's an example of counting inversions in an array using the divide and conquer approach in C++

#include<iostream>
#include<vector> 

using namespace std;

int mergeAndCount(vector<int>& arr, int left, int mid, int right) {
    int inversions = 0;

    // Create temporary arrays to store the left and right subarrays
    vector<int> leftArr(mid - left + 1);
    vector<int> rightArr(right - mid);

    // Copy data to temporary arrays
    for (int i = 0; i < leftArr.size(); i++) {
        leftArr[i] = arr[left + i];
    }
    for (int i = 0; i < rightArr.size(); i++) {
        rightArr[i] = arr[mid + 1 + i];
    }

    // Merge the two subarrays and count inversions
    int i = 0, j = 0, k = left;
    while (i < leftArr.size() && j < rightArr.size()) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        }
        else {
            arr[k] = rightArr[j];
            j++;
            inversions += (mid - i + 1);  // Count inversions
        }
        k++;
    }

    // Copy the remaining elements of leftArr, if any
    while (i < leftArr.size()) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    // Copy the remaining elements of rightArr, if any
    while (j < rightArr.size()) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }

    return inversions;
}

int mergeSortAndCount(vector<int>& arr, int left, int right) {
    int inversions = 0;

    if (left < right) {
        int mid = left + (right - left) / 2;

        // Recursively divide the array and count inversions
        inversions += mergeSortAndCount(arr, left, mid);
        inversions += mergeSortAndCount(arr, mid + 1, right);

        // Merge the sorted subarrays and count inversions
        inversions += mergeAndCount(arr, left, mid, right);
    }

    return inversions;
}

int countInversions(vector<int>& arr) {
    return mergeSortAndCount(arr, 0, arr.size() - 1);
}

int main() {
    vector<int> arr = {5, 2, 8, 1, 9};
    int inversionCount = countInversions(arr);
    cout << "Number of inversions: " << inversionCount << endl;

    return 0;
}

Output:

Number of inversions: 4

In this code, the function mergeAndCount merges two sorted subarrays and counts the inversions that occur during the merging process. This function uses recursion to divide the array into smaller subarrays, applies merge sort to each subarray, and counts the inversions. Finally, it initializes the merge sort process and returns the total count of inversions in the array.

This program demonstrates the usage by providing an example array [5,2,8,1,9] and prints the number of inversions.

The overall time complexity of the divide and conquer approach for counting inversions is O(n log n). The space complexity of the code is O(n) due to the temporary arrays used for merging.

Conclusion

Inversions play a vital role in various algorithmic applications, mainly sorting like merge sort. In text processing and data analysis, inversions can help identify similarities and differences between two sequences or documents. You can now count easily count inversions in an array with implementation in C++.