Count Inversions in Array
What you'll learn: How to efficiently count pairs where a larger element appears before a smaller one using a modified mergesort.
The Problem
An inversion in an array is a pair of indices (i, j) where i < j but array[i] > array[j]. In other words, two elements are "out of order" relative to their positions. For example, in [3, 1, 2], there are two inversions: (3,1) and (3,2).
Counting inversions tells you how "unsorted" an array is—useful for measuring similarity between rankings or detecting how far data is from being sorted.
The Naive Approach
You could check every pair with nested loops—that's O(n²). But we can do better using divide and conquer.
Modified Mergesort Solution
Remember mergesort? It splits the array, sorts each half, then merges. During the merge step, we can count inversions cleverly:
- Left-half inversions: Count recursively in the left half
- Right-half inversions: Count recursively in the right half
- Split inversions: When merging, if we pick an element from the right subarray before exhausting the left, all remaining left elements form inversions with it (they're larger and appear earlier in the original array)
Analogy: Imagine two sorted stacks of numbered cards. When you pick from the right stack first, you know every card still in the left stack is bigger and was originally before it—those are your inversions!
The merge operation naturally finds split inversions while maintaining O(n log n) time complexity.
Key Takeaway: By counting split inversions during mergesort's merge step, you count all inversions in O(n log n) time—the same as just sorting the array.