LeetCode 493 Reverse Pairs - Why Naive Fails

Checking all pairs $(i, j)$ where $i < j$ and $nums[i] > 2 \times nums[j]$ takes $O(n^2)$. For $n = 5 \times 10^4$, that's $2.5 \times 10^9$ operations.

Example: nums = [1, 3, 2, 3, 1]. Pairs to check: $(0,1), (0,2), ..., (3,4)$. Most aren't reverse pairs.

Modified merge sort: while merging two sorted halves, count pairs where left element $> 2 \times$ right element. Both halves are sorted, so use two pointers. $O(n \log n)$.