How Many At Once
Counting inversions by modified merge sort. Both halves are already sorted; tmp collects the merged run.
long long cnt = 0;
int i = lo, j = mid + 1, k = 0;
while (i <= mid && j <= hi) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++];
} else {
cnt += /* ??? */;
tmp[k++] = a[j++];
}
}
Which expression makes cnt the exact number of inversions closed by this merge?
Sign in to answer questions and track your progress
Sign In