Given an integer array arr[] of length n, the task is to find the inversion count of arr[].
Two elements, arr[i] and arr[j], form an inversion if arr[i] > arr[j] and i < j. If the array is already sorted, then the inversion count is 0.
If an array is sorted in the reverse order, then the inversion count is the maximum.
Example 1
Input: arr[] = {2, 4, 1, 3, 5}, n = 5, Output: 3
Example 2
Input: arr[] = {1, 20, 6, 4, 5}, n = 5, Output: 5
Solutions
Method 1: In O(n log n) time
In this approach, we use modified merge sort such that every time a greater element is found in the left array, we increment the count by one and return the count at the end.
If left[i] is greater than right[j], then there are ((mid + i) - (l + 1)) inversions because left and right subarrays are sorted, so all the remaining elements in left-subarray (right[mid+i] to right[mid]) will be greater than right[j].
Complexity
The time complexity of this solution is O(n) and space complexity is O(n log n).
Method 2: In O(n^2) time
Traverse through the array from left to right, and for each element, find the number of smaller elements on its right side. Add up the count of inversions for every index and print.
Complexity
The time complexity of this solution is O(n) and space complexity is O(n^2).