# Implement Count Inversion in an Array

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

Back to: Data Structure > Data Structure - Arrays