I'm designing an algorithm to do the following: Given array A[1... n], for every i < j, find all inversion pairs such that A[i] > A[j]. I'm using merge sort and copying array A to array B and then comparing the two arrays, but I'm having a difficult time seeing how I can use this to find the number of inversions. Any hints or help would be greatly appreciated.
ベストアンサー1
So, here is O(n log n) solution in java.
long merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0;
long count = 0;
while (i < left.length || j < right.length) {
if (i == left.length) {
arr[i+j] = right[j];
j++;
} else if (j == right.length) {
arr[i+j] = left[i];
i++;
} else if (left[i] <= right[j]) {
arr[i+j] = left[i];
i++;
} else {
arr[i+j] = right[j];
count += left.length-i;
j++;
}
}
return count;
}
long invCount(int[] arr) {
if (arr.length < 2)
return 0;
int m = (arr.length + 1) / 2;
int left[] = Arrays.copyOfRange(arr, 0, m);
int right[] = Arrays.copyOfRange(arr, m, arr.length);
return invCount(left) + invCount(right) + merge(arr, left, right);
}
This is almost normal merge sort, the whole magic is hidden in merge function. Note that while sorting, algorithm remove inversions. While merging, algorithm counts number of removed inversions (sorted out one might say).
The only moment when inversions are removed is when algorithm takes element from the right side of an array and merge it to the main array. The number of inversions removed by this operation is the number of elements remaining from the the left array to be merged.
Hope it's explanatory enough.