Challenge: Inversion Count in a List

In this lesson, we will solve the problem of counting the number of inversions in a list.

We'll cover the following

What is inversion count?

Inversion count represents how far or close a list is from being sorted. If a list 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 lst[i] > lst[j], then there is an inversion in the list.

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.