Count Inversions in an Array

Introduction

Inversion Count for an array indicates how far (or close) the array is from being sorted.

If the array is already sorted, then the inversion count is 0.
If the array is sorted in reverse order, the inversion count is the maximum.

Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

Examples

Example 1:

Input: arr[] = {8, 4, 2, 1}
Output: 6
Explanation: Given array has six inversions: (8, 4), (4, 2), (8, 2), (8, 1), (4, 1), (2, 1).

Example 2:

Input: arr[] = {3, 1, 2}
Output: 2
Explanation: Given array has two inversions: (3, 1), (3, 2).

Simple Approach

Traverse through the array, and for every index, find the number of smaller elements on its right side of the array. This can be done using a nested loop. Sum up the counts for all indices in the array and print the sum.

Steps to implement

Traverse through the array from start to end.
For every element, find the count of elements smaller than the current number up to that index using another loop.
Sum up the count of inversion for every index.
Print the count of inversions.

Implementation

function getInvCount(arr) {
    let inv_count = 0;
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                inv_count++;
            }
        }
    }
    return inv_count;
}
 
// Example usage
let arr1 = [1, 2, 0, 4, 3, 1];
console.log(getInvCount(arr1)); // Output: 4

Complexity Analysis (Simple Approach)

Time Complexity: O(N²) - Two nested loops are needed to traverse the array from start to end.
Auxiliary Space: O(1) - No extra space is required.

Count Inversions using Merge Sort

This algorithm is a Divide and Conquer algorithm and is a modified version of the Merge Sort algorithm.

The idea is to count inversions while merging two halves. During the merge step, if we find that an element in the left half is greater than an element in the right half, it means all remaining elements in the left half are also greater than the element in the right half (because the left half is sorted). Thus, we can count multiple inversions at once.

Steps for Merge Sort approach

The idea is similar to merge sort: divide the array into two equal or almost equal halves in each step until the base case is reached.
Create a function merge that counts the number of inversions when two halves of the array are merged. Create two indices i and j (i is the index for the first half, and j is an index of the second half).
If a[i] is greater than a[j], then there are (mid - i) inversions. Because left and right subarrays are sorted, all the remaining elements in the left-subarray (a[i+1], a[i+2] ... a[mid]) will be greater than a[j].
Create a recursive function to divide the array into halves and find the answer by summing:
- The number of inversions in the first half
- The number of inversions in the second half
- The number of inversions by merging the two halves
The base case of recursion is when there is only one element in the given half.
Print the answer.

Implementation

function mergeAndCount(arr, l, m, r) {
    // Left subarray
    let left = [];
    for (let i = l; i < m + 1; i++) {
        left.push(arr[i]);
    }
    
    // Right subarray
    let right = [];
    for (let i = m + 1; i < r + 1; i++) {
        right.push(arr[i]);
    }
    
    let i = 0, j = 0, k = l, swaps = 0;
    
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
            // Increment swap count by the number of remaining elements in left half
            swaps += (m + 1) - (l + i);
        }
    }
    
    // Copy remaining elements
    while (i < left.length) {
        arr[k++] = left[i++];
    }
    while (j < right.length) {
        arr[k++] = right[j++];
    }
        
    return swaps;
}
 
function mergeSortAndCount(arr, l, r) {
    let count = 0;
    if (l < r) {
        let m = Math.floor((l + r) / 2);
        
        // Count inversions in the left half
        count += mergeSortAndCount(arr, l, m);
        
        // Count inversions in the right half
        count += mergeSortAndCount(arr, m + 1, r);
        
        // Count inversions during merge
        count += mergeAndCount(arr, l, m, r);
    }
    return count;
}
 
// Example usage
let arr2 = [1, 2, 0, 4, 3, 1];
console.log(mergeSortAndCount(arr2, 0, arr2.length - 1)); // Output: 4

Complexity Analysis (Merge Sort Approach)

Time Complexity: O(N log N) - The algorithm used is divide and conquer. In each level, one full array traversal is needed, and there are log N levels, so the time complexity is O(N log N).
Auxiliary Space: O(N) - We need a temporary array to merge the elements.

Note: Time complexity is similar to Merge Sort but it requires extra space. If we have to sort the array and find inversion count, then use merge sort, otherwise use binary indexed tree for inversion count if strict space constraints apply.

Quick Sort Union of Two Arrays