In this article, we will implement count inversions in an array, with an explanation of the process. First, let’s see what inversion is. Given an array of n elements, an inversion is defined as the pair (Array[i], Array[j]) if i < j and Array[i]>Array[j]. Put, it tells us how many conversions we need to do to sort the array. Consider the following example.

Array = 4, 2, 1, 7, 9, 8
Inversions = (4, 2), (4, 1), (2, 1), (9, 8)

Our problem is to find the number of inversions in an array. In the above example, the inversion count is equal to 4. So how can we solve this problem?

Naïve Approach

A simple way to find the inversion count is to traverse the array and compare all pairs. Compare each item present at index i with all elements after it. If it is greater, then increase the count.

This approach is straightforward. However, it has a time complexity of O(n2).

Code

Consider the following code.

def countIversionNaive(array, n):
  count_inversion = 0
  for i in range(0, n-1):
    for j in range(i+1,n):
      if array[i] > array[j]: #if the inversion condition satisfies then increase the count
        count_inversion += 1

  return count_inversion 

Now call the function

array = [4, 2, 1, 7, 9, 8] 
count = countIversionNaive(array,len(array)) 
print("Inversion Count:", count)

Output

Inversion Count: 4

We can obtain a better solution than this by modifying the merge sort algorithm a little bit. It is more efficient and provides a time complexity of O(nlogn).

Modified Merge Sort

Now let’s discuss the modified version of the merge sort. More specifically, we will change the merge method. We recursively divide an array into two equal (or roughly equal) parts until its size becomes one.

Then, we merge the left and right halves. This is a trickier part because we perform the sorting as well as the inversion count here. We start at subarrays of length 1 at the bottom and go to the top by sorting the left and right parts. Therefore, both given subarrays will be sorted at any stage in the merge method.

We create two pointers, i and j, for the left and right halves, respectively. Initially, both point to the start, i.e., i = 0 and j = 0. If the value at index i is less than or equal to the item present at index j, we take the former for merging and increment i by 1. No inversion will be done here.

Otherwise, we take the element at index j for merging. Here, we need to increase the inversion count because i < j and array[i]>array[j]. Furthermore, all values after index i will also be greater than array[j] since subarrays are sorted. Hence, the inversion count will be equal to the length of the subarray – index i. We update the count and increment j as well.

Code

Consider the following implementation.

def merge_count(array, l, r, m):
  global count_inversion

  #create temporary left and right array
  temp_left=array[l:m+1]
  temp_right=array[m+1:r+1]
  left_size = len(temp_left)
  right_size = len(temp_right)
  i=0 #pointer for left
  j=0 #pointer for right 
  k=l #pointer to make changes in the original array
 
 #add sorted elements from the subarrays
  while (i<left_size and j<right_size):
    if (temp_left[i] <= temp_right[j]):  #add elements from left sub array
      array[k] = temp_left[i]
      k +=1
      i += 1 #increase the left sub array pointer
    else: #add elements from right sub array
      array[k] = temp_right[j]
      count_inversion += left_size-i
      k +=1
      j += 1 #increase the right sub array pointer
  
  #copy the remaining elements if they exist
  if i<left_size: 
    array[k: k+(left_size-i)] =  temp_left[i: left_size]
  elif j<right_size:
    array[k: k+(right_size-j)] =  temp_right[j: right_size]


def countInversion(array, l, r):
  global count_inversion
  if l < r:
    mid = (l+r)//2
    countInversion(array, l, mid) #left part
    countInversion(array, mid+1, r) #right part
    merge_count(array, l, r, mid)

Now call the function

array = [4, 2, 1, 7, 9, 8]
count_inversion=0
countInversion(array, 0, len(array)-1)
print("Inversion Count:", count_inversion)

Output

Inversion Count: 4