Counting Inversions in an Array

Counting Inversions in an Array

December 17, 2023
medium
mergesort

Problem #

Given an array of integers, count the number of inversions, where an inversion is a pair of integers (i, j) such that i < j and arr[i] > arr[j].

Solution #

To solve the problem of counting the number of inversions in an array, where an inversion is defined as a pair of indices ((i, j)) such that (i < j) and (\text{arr}[i] > \text{arr}[j]), we can use a modified version of the merge sort algorithm. This algorithm is efficient for such problems because it naturally compares elements in a divide-and-conquer manner.

The basic idea is to enhance the merge step of the merge sort algorithm so that, in addition to sorting, it also counts the inversions. When elements from the right half (which are supposed to be greater if the array were sorted) are placed before elements in the left half, we have found inversions. The number of such inversions is equal to the number of elements remaining in the left half, because all of these elements are greater than the elements from the right half.

Here’s a Python implementation of this idea:

def mergeSortAndCount(arr, temp, left, right):
    # Initialize inversion count
    inv_count = 0

    # If there are elements to be sorted
    if left < right:
        # Find the mid point
        mid = (left + right) // 2

        # Recursively split and count inversions for left half
        inv_count += mergeSortAndCount(arr, temp, left, mid)

        # Recursively split and count inversions for right half
        inv_count += mergeSortAndCount(arr, temp, mid + 1, right)

        # Merge two halves and add inversions found during merge
        inv_count += mergeAndCount(arr, temp, left, mid, right)

    return inv_count

def mergeAndCount(arr, temp, left, mid, right):
    i = left  # Starting index for left subarray
    j = mid + 1  # Starting index for right subarray
    k = left  # Starting index for merged subarray
    inv_count = 0

    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]
            k += 1
            i += 1
        else:
            # Inversion will occur
            temp[k] = arr[j]
            inv_count += (mid - i + 1)  # Count inversions
            k += 1
            j += 1

    # Copy remaining elements of left subarray (if any)
    while i <= mid:
        temp[k] = arr[i]
        k += 1
        i += 1

    # Copy remaining elements of right subarray (if any)
    while j <= right:
        temp[k] = arr[j]
        k += 1
        j += 1

    # Copy back the merged elements to the original array
    for i in range(left, right + 1):
        arr[i] = temp[i]

    return inv_count

def countInversions(arr):
    n = len(arr)
    temp = [0] * n
    return mergeSortAndCount(arr, temp, 0, n - 1)

# Example usage
arr = [1, 20, 6, 4, 5]
print("Number of inversions are", countInversions(arr))

This code defines a function countInversions which uses a helper function mergeSortAndCount and mergeAndCount to count the inversions. The mergeSortAndCount function recursively splits the array and counts inversions in the subarrays and during the merge process. The mergeAndCount function performs the merge operation and counts the inversions occurring during the merge.