Count Inversions

Difficulty: Hard · Topic: Sorting

An inversion is a pair of indices i < j with nums[i] > nums[j]. The number of inversions measures how far an array is from sorted. Counting them in O(n²) is easy; do it in O(n log n) by counting during a merge sort — when an element from the right half is taken before elements remaining in the left half, each of those left elements forms an inversion with it.

Examples

count_inversions([1,2,3])
→ 0

Already sorted — no inversions.

count_inversions([3,2,1])
→ 3

(3,2), (3,1), (2,1).

count_inversions([1,3,2])
→ 1

Target complexity: time O(n log n), space O(n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.