An inversion is a pair of numbers at indices i and j, such that i < j and number[i] > number[j]. Inversion count is number of steps required to apply on array to get it sorted. If array is sorted, then number of inversions are ‘zero’. But if array is in reverse order then number of inversion would be maximum. i.e. n(n−1)/2.
Example :
Input: A sequence of numbers. (1, 5, 6, 4, 20). Output: The number of inversions required to arrange the numbers into ascending order. Here the number of inversions are 2. First inversion: (1, 5, 4, 6, 20) Second inversion: (1, 4, 5, 6, 20)
Inversion count in the array can be found using modified ‘merge’ step in the merge sort algorithm.