Small example
Input
arr = [2, 4, 1, 3, 5]
Output
3
Inversions are (2,1), (4,1), (4,3) -> total 3.
Full lesson preview
Count inversions using modified merge sort
Count the number of inversions in an array by augmenting merge sort to count cross-pairs.
Python practice25 minSearching & SortingAdvancedLast updated March 25, 2026
Problem statement
An inversion in an array arr is a pair (i, j) such that i < j and arr[i] > arr[j]. Given an integer list arr, return the number of inversions in the array. Implement an algorithm based on merge sort that counts inversions while merging.
Task
Implement a divide-and-conquer algorithm that counts inversions in O(n log n) time and O(n) extra space.
Examples
Input format
Function call: count_inversions(arr) where arr is a list of integers.
Output format
Return an integer count of inversions.
Constraints
- 0 <= len(arr) <= 10^5
- Values fit in standard Python int
- Aim for O(n log n) time and O(n) extra space
Samples
Sample 1
Input
count_inversions([1, 3, 2])
Output
1
Only inversion is (3,2).