Count inversions lite

Count how many pairs of elements are out of order in a list.

inversions sorting merge sort counting

An inversion is a pair of indices (i, j) such that i < j and arr[i] > arr[j]. For example, in [3, 1, 2] there are two inversions: (0,1) and (0,2). Write a function `count_inversions(arr)` that takes a list of integers and returns the total number of inversions. The list will not contain duplicate elements.

Implement the function without modifying the input list. Your solution should run in O(n log n) time (e.g., using merge sort).

Constraints

- 0 <= len(arr) <= 10^5
- Each element is an integer in the range [-10^9, 10^9]
- All elements are distinct

Example

>>> count_inversions([3, 1, 2])
2
>>> count_inversions([5, 4, 3, 2, 1])
10
>>> count_inversions([1, 2, 3, 4])
0
>>> count_inversions([])
0

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about how merge sort can count inversions while sorting.

Whenever you take an element from the right half before the left half, all remaining elements in the left half are inversions with it.

Use a helper function that returns both the sorted list and the inversion count.

The naive O(n^2) double loop will be too slow for large inputs.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.