Challenge: Inversion Count in an Array

Calculate the number of inversions in an array.

We'll cover the following

What is the inversion count?

Inversion count represents how far or close an array is from being sorted. If an array is sorted, the inversion count will be 0. But if it’s sorted in the reverse order, the inversion count will be maximum.

Consider indices i and j, such that i < j and arr[i] > arr[j], then there is an inversion in the array.

For example:

 [9, 5, 6, 11, 8, 10] 

 Number of inversions = 5 

 i-e: [9, 5], [9, 6], [9, 8], [11, 8], [11, 10]

Have a look at the following illustration for a better understanding:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.