# Counting Inversions in an Array

##### December 17, 2023

## 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.