Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j
Example:
Input: arr[] = {8, 4, 2, 1}
Output: 6
Explanation: Given array has six inversions:
(8,4), (4,2),(8,2), (8,1), (4,1), (2,1).
Input: arr[] = {3, 1, 2}
Output: 2
Explanation: Given array has two inversions:
(3, 1), (3, 2)
class GFG {
// Some Question
// Why this works ?
// 1) When we are merging the sorted parts, then we have already taken care of
// inversions within each part, therefore we only need to take care of
// inversions with the other part
// 2) We need to understand that when we compare i & j in sorted order, you
// might think that we need inversion in unsorted array
// But remember that 1st part is sorted within itself that means that value at
// index i, will be before j value in the original array aswell
public static long merge(int[] arr, int start, int end) {
int mid = start + (end - start) / 2;
int[] holderArr = new int[end - start + 1];
int pointer1 = start, pointer2 = mid + 1, index = 0;
long inversions = 0;
while (pointer1 <= mid && pointer2 <= end) {
if (arr[pointer1] <= arr[pointer2])
holderArr[index++] = arr[pointer1++];
// If arr[i] > arr[j], then all the elements will be > arr[j]
// because it is sorted array
else {
inversions += (mid - pointer1 + 1);
holderArr[index++] = arr[pointer2++];
}
}
while (pointer1 <= mid)
holderArr[index++] = arr[pointer1++];
while (pointer2 <= end)
holderArr[index++] = arr[pointer2++];
// Copying the changes into original array
for (int i = start; i <= end; i++)
arr[i] = holderArr[i - start];
return inversions;
}
public static long mergeSort(int[] arr, int start, int end) {
if (start >= end)
return 0L;
int mid = start + (end - start) / 2;
long leftInversions = mergeSort(arr, start, mid);
long rightInversions = mergeSort(arr, mid + 1, end);
return leftInversions + rightInversions + merge(arr, start, end);
}
public static long countInversions(int[] arr) {
return mergeSort(arr, 0, arr.length - 1);
}
}