Count Inversions Using Modified Merge Sort
Count the number of inversions in an array — pairs where a[i] > a[j] and i < j — by counting cross-split inversions during the merge step.
What is an Inversion?
An inversion in an array is a pair of indices (i, j) where i < j but a[i] > a[j] — a larger element appears before a smaller one. For example, in [3, 1, 2], the inversions are (3,1) and (3,2), so there are 2 inversions. A sorted array has 0 inversions. A reverse-sorted array of n elements has n(n-1)/2 inversions. Counting inversions measures how far an array is from sorted order.
arr = [3, 1, 2]
# Inversions: pairs (i,j) where i<j and arr[i]>arr[j]
inversions = []
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
inversions.append((arr[i], arr[j]))
print('Inversions in', arr, ':', inversions)
print('Count:', len(inversions)) # 2
# Maximum inversions in n-element array:
import math
n = 5
print(f'Max inversions for n={n}: {n*(n-1)//2}') # 10 for [5,4,3,2,1]Naive O(n²) Approach
The brute-force approach checks all pairs (i, j) with i < j and counts those where a[i] > a[j]. This is O(n²) time and O(1) space. For n = 10⁵, this means 5 × 10⁹ comparisons — too slow. The divide and conquer approach using modified merge sort solves it in O(n log n). The key insight is that during the merge step of merge sort, we can count cross-split inversions efficiently.
def count_inversions_brute(arr):
n = len(arr)
count = 0
for i in range(n):
for j in range(i + 1, n):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_brute([3, 1, 2])) # 2
print(count_inversions_brute([5, 4, 3, 2, 1])) # 10
print(count_inversions_brute([1, 2, 3, 4, 5])) # 0
print(count_inversions_brute([2, 4, 1, 3, 5])) # 3All lessons in this course
- Divide and Conquer Template
- Count Inversions Using Modified Merge Sort
- Majority Element: Boyer-Moore Voting
- Median of Two Sorted Arrays