Count Inversions
WHAT IT SAYS
Count the pairs (i, j) with i < j and a[i] > a[j] — the number of swaps a bubble sort would need to sort the array.
WHAT IT'S REALLY ASKING
"Cut the array in half. Every inverted pair is either entirely on the left, entirely on the right, or straddling the cut — and the first two are just smaller copies of the same problem. So the only real question is the straddlers. And if both halves happened to be sorted, how expensive is a straddler really?"
Check every pair
O(n^2) time, O(1) spaceTwo nested loops over i < j, incrementing a counter whenever a[i] > a[j]. Correct by definition, and it will time out.
WHERE THE WORK IS WASTED — Every comparison buys exactly one bit about exactly one pair, but the answers are enormously correlated. If a[i] > a[j] and a[j] > a[k], transitivity already settles a[i] > a[k] — and the inner loop asks anyway. Order is a global structure, and the double loop insists on rediscovering it one pair at a time, from scratch, forever.
Split the pairs, sort the halves, count the crossings free.
Cut at the midpoint and classify every pair (i < j) by where its two members land: both left, both right, or one on each side. Those three classes are disjoint and exhaustive, so inv(whole) = inv(left) + inv(right) + cross(left, right). The recursion handles the first two terms. Everything hinges on the third. Now the licence that makes this work, and it is easy to miss. The cross count asks: how many pairs have a left element greater than a right element? That is a question about the CONTENTS of the two halves — the multisets — and not about the order within them. Shuffle the left half however you like and the cross count does not change. Which means the recursion is FREE to sort each half as it goes, because sorting cannot corrupt the only quantity you still need from them. And once both halves are sorted, counting the crossings stops being a search. Merge them. Whenever you pop an element from the RIGHT half, every element still remaining in the left half is greater than it — both halves are sorted, so the left half's remaining elements are all at least as large as the one your left pointer is on, and that one already lost the comparison. So one pop does not certify one inversion. It certifies (elements remaining in the left half) inversions, all at once, in O(1). That is the whole algorithm: the merge you needed anyway to maintain sortedness is exactly the sweep that counts the straddlers. The bookkeeping and the answer are the same pass.
Merge sort, counting as you merge
O(n log n) time, O(n) auxiliary space for the merge bufferRecursively sort each half, accumulating the inversion counts they return. Then merge: when the left element is smaller or equal, take it; when the RIGHT element is smaller, take it and add (mid - i + 1) to the count — the number of left-half elements still unconsumed, every one of which is greater than what you just popped. The total is left + right + crossings.
Count Across the Cut
YOU'LL SEE IT AGAIN WHEN
- The answer counts PAIRS satisfying an order relation, and pairs decompose cleanly into left / right / straddling under any split.
- The straddling count depends only on the contents of each side, not their internal arrangement — so the recursion is free to reorder them.
- Under sortedness, one comparison would certify an entire block of pairs at once, while the naive loop certifies them one at a time.