An inversion is a pair of positions i < j with a[i] > a[j]: two numbers in the wrong order. Count the inversions in n numbers. A double loop over all pairs works, but is O(n²); do it in O(n log n) with merge sort.
What to build
A merge sort that counts inversions as it merges.
Requirements
- Sort with merge sort, not with two nested loops.
- When an item from the right half is copied first, add the number of items still waiting in the left half.
- Keep the count in a
long long.
Input
The first line has n (1 ≤ n ≤ 1000). The second line has the n numbers.
Output
The number of inversions.
Constraints
1 ≤ n ≤ 1000.
Example
Input:
5
2 4 1 3 5
Output:
3
Why it works
Both halves are sorted, so an item from the right half that is copied first is smaller than everything left in the left half. All of those pairs are inversions, and they are counted in one step.
Examples
5 2 4 1 3 5
3
4 1 2 3 4
0
Hints
Hint 1
Sort with merge sort, and count while merging two sorted halves.
Hint 2
When the right half's item is copied before the left half's, it is smaller than every item still waiting in the left half: add (mid - i + 1) to the count.
Hint 3
Use long long for the count.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int a[1000], tmp[1000];
long long inversions = 0;
void merge(int lo, int mid, int hi) {
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++];
} else {
inversions += mid - i + 1; // a[j] is smaller than every a[i .. mid]
tmp[k++] = a[j++];
}
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
for (k = lo; k <= hi; k++) a[k] = tmp[k];
}
void merge_sort(int lo, int hi) {
if (lo >= hi) return;
int mid = (lo + hi) / 2;
merge_sort(lo, mid);
merge_sort(mid + 1, hi);
merge(lo, mid, hi);
}
int main(void) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
merge_sort(0, n - 1);
printf("%lld\n", inversions);
return 0;
}