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.
Count Inversions Using Modified Merge Sort is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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])) # 3The Merge Sort Insight
During a merge of two sorted halves L and R, if we pick element R[j] over L[i] (because R[j] < L[i]), then all remaining elements in L from index i onward are also greater than R[j]. This is because L is sorted. So each time we take from the right half, we count len(L) - i cross-half inversions. This counting is free — it happens during the normal merge.
# During merge of [1, 3, 5] and [2, 4, 6]:
# Compare L[0]=1 vs R[0]=2: take L[0]=1, no inversions
# Compare L[1]=3 vs R[0]=2: take R[0]=2, inversions += len(L)-1 = 2 (3>2, 5>2)
# Compare L[1]=3 vs R[1]=4: take L[1]=3, no inversions
# Compare L[2]=5 vs R[1]=4: take R[1]=4, inversions += len(L)-2 = 1 (5>4)
# Compare L[2]=5 vs R[2]=6: take L[2]=5, no inversions
# Take R[2]=6
# Total cross-inversions = 2 + 1 = 3
print('Cross-inversions identified during merge: 3')Modified Merge Sort Implementation
Modify merge sort to return both the sorted array and the inversion count. The total inversions = left half inversions + right half inversions + cross inversions found during merge. The base case returns (single element, 0 inversions). The merge function counts inversions as it merges. Total time: O(n log n).
def count_inversions(arr):
def merge_sort_count(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, left_count = merge_sort_count(arr[:mid])
right, right_count = merge_sort_count(arr[mid:])
merged, cross_count = merge_count(left, right)
return merged, left_count + right_count + cross_count
def merge_count(left, right):
result, count = [], 0
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
count += len(left) - i # all remaining in left are inversions
result += left[i:] + right[j:]
return result, count
_, total = merge_sort_count(arr)
return total
print(count_inversions([3, 1, 2])) # 2
print(count_inversions([5, 4, 3, 2, 1])) # 10
print(count_inversions([2, 4, 1, 3, 5])) # 3Tracing the Algorithm
Trace [2, 4, 1, 3]: Divide into [2, 4] and [1, 3]. Left sub-sort: [2, 4] → sorted [2,4], 0 inversions. Right sub-sort: [1, 3] → sorted [1,3], 0 inversions. Merge [2,4] and [1,3]: take 1 (count += 2 for 2>1 and 4>1), take 2 (no count), take 3 (count += 1 for 4>3), take 4. Cross inversions = 3. Total = 0+0+3 = 3. Verify: pairs (2,1), (4,1), (4,3) = 3 inversions. ✓
def count_with_trace(arr):
def ms(arr, depth=0):
indent = ' ' * depth
if len(arr) <= 1: return arr, 0
mid = len(arr) // 2
L, lc = ms(arr[:mid], depth+1)
R, rc = ms(arr[mid:], depth+1)
merged, cc = merge_c(L, R)
print(f'{indent}merge({L},{R}) → cross={cc}')
return merged, lc + rc + cc
def merge_c(L, R):
res, c, i, j = [], 0, 0, 0
while i < len(L) and j < len(R):
if L[i] <= R[j]: res.append(L[i]); i += 1
else: res.append(R[j]); j += 1; c += len(L) - i
return res + L[i:] + R[j:], c
_, total = ms(arr)
return total
print('Total inversions:', count_with_trace([2, 4, 1, 3]))Why Cross Inversions Are Captured Correctly
Correctness: any inversion pair (a[i], a[j]) where i < j belongs to exactly one of three categories: (1) Both in the left half — counted by recursive left call. (2) Both in the right half — counted by recursive right call. (3) Left half element > right half element — counted during merge as cross inversions. Categories are mutually exclusive and exhaustive, so no inversion is double-counted or missed. This partition argument is the standard D&C correctness proof.
# Verification: compare with brute force on random arrays
import random
def count_brute(arr):
n = len(arr)
return sum(1 for i in range(n) for j in range(i+1,n) if arr[i]>arr[j])
def count_dc(arr):
def ms(a):
if len(a)<=1: return a, 0
m=len(a)//2
L,lc=ms(a[:m]); R,rc=ms(a[m:])
res,c,i,j=[],0,0,0
while i<len(L) and j<len(R):
if L[i]<=R[j]: res.append(L[i]);i+=1
else: res.append(R[j]);j+=1;c+=len(L)-i
return res+L[i:]+R[j:],(lc+rc+c)
return ms(arr)[1]
for _ in range(100):
arr = random.choices(range(20), k=random.randint(1,10))
assert count_dc(arr[:]) == count_brute(arr), 'MISMATCH!'
print('All 100 random tests passed!')Applications of Inversion Count
Inversions measure sortedness. Applications: (1) Ranking correlation: Kendall tau distance between two ranked lists is the number of inversions. (2) Insertion sort efficiency: insertion sort makes exactly as many swaps as there are inversions. (3) Bubble sort analysis: each bubble sort pass reduces inversions; number of passes needed equals the number of inversions. (4) Puzzle solvability: an 8-puzzle or 15-puzzle is solvable iff the number of inversions has a specific parity.
# Kendall tau: number of inversions between two rankings
# Useful for comparing search result rankings or recommendation systems
def kendall_tau(rank1, rank2):
'''Count inversions where rank1 and rank2 disagree on relative order.'''
# Map rank2 positions to create a comparison sequence
pos = {v: i for i, v in enumerate(rank2)}
# Convert rank1 to position-in-rank2 ordering
arr = [pos[v] for v in rank1]
return count_inversions(arr)
def count_inversions(arr):
def ms(a):
if len(a)<=1: return a,0
m=len(a)//2; L,lc=ms(a[:m]); R,rc=ms(a[m:])
res,c,i,j=[],0,0,0
while i<len(L) and j<len(R):
if L[i]<=R[j]: res.append(L[i]);i+=1
else: res.append(R[j]);j+=1;c+=len(L)-i
return res+L[i:]+R[j:],(lc+rc+c)
return ms(arr[:])[1]
print(kendall_tau([1,2,3],[3,1,2])) # measures disagreementRelated: Count Smaller Numbers After Self
Count Smaller Numbers After Self (LeetCode 315) asks for each element: how many elements to its right are smaller? This is a per-element inversion count. It can be solved with the same modified merge sort but tracking which original indices are counted. Alternatively, use a Binary Indexed Tree (Fenwick Tree) or a merge sort with index tracking. The D&C approach runs in O(n log n).
def count_smaller(nums):
n = len(nums)
result = [0] * n
indexed = list(enumerate(nums))
def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i][1] <= right[j][1]:
# left[i] is placed; j elements from right are smaller and to the right
result[left[i][0]] += j
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
while i < len(left):
result[left[i][0]] += j # all of right is smaller
merged.append(left[i]); i += 1
return merged + right[j:]
merge_sort(indexed)
return result
print(count_smaller([5, 2, 6, 1])) # [2, 1, 1, 0]Reverse Pairs
Reverse Pairs (LeetCode 493) counts pairs (i, j) where i < j and nums[i] > 2 × nums[j]. The standard inversion count uses nums[i] > nums[j]. Here, the threshold changes to 2 × nums[j]. Modify the merge sort: count across splits before merging (use a two-pointer to count while left half still has valid elements), then merge normally. O(n log n) total.
def reverse_pairs(nums):
def merge_sort_count(arr):
if len(arr) <= 1: return arr, 0
mid = len(arr) // 2
L, lc = merge_sort_count(arr[:mid])
R, rc = merge_sort_count(arr[mid:])
# Count cross pairs: L[i] > 2*R[j]
j = 0
cross = 0
for l_val in L:
while j < len(R) and l_val > 2 * R[j]:
j += 1
cross += j
# Normal merge (separate from count)
merged = []
i = jj = 0
while i < len(L) and jj < len(R):
if L[i] <= R[jj]: merged.append(L[i]); i += 1
else: merged.append(R[jj]); jj += 1
merged += L[i:] + R[jj:]
return merged, lc + rc + cross
return merge_sort_count(nums)[1]
print(reverse_pairs([1, 3, 2, 3, 1])) # 2
print(reverse_pairs([2, 4, 3, 5, 1])) # 3Global Inversion Count vs Local
Global and Local Inversions (LeetCode 775): given a permutation of 0..n-1, determine if the number of global inversions (all pairs i<j with a[i]>a[j]) equals the number of local inversions (adjacent pairs). Key insight: every local inversion is also global, so global ≥ local. They are equal iff there are no non-adjacent inversions — meaning no element is more than 1 position away from its sorted index. This reduces to checking abs(a[i] - i) ≤ 1 for all i.
def is_ideal_permutation(A):
'''Global inversions == local inversions
iff no element is more than 1 position from its sorted index.'''
return all(abs(a - i) <= 1 for i, a in enumerate(A))
print(is_ideal_permutation([1, 0, 2])) # True
print(is_ideal_permutation([1, 2, 0])) # False (A[0]=1 is far from 2, A[2]=0 is far)
# Verification with inversion counts
print(count_inversions([1, 0, 2])) # 1 (global)
local1 = sum(1 for i in range(len([1,0,2])-1) if [1,0,2][i]>[1,0,2][i+1])
print('local:', local1) # 1 (equal)
def count_inversions(arr):
def ms(a):
if len(a)<=1: return a,0
m=len(a)//2; L,lc=ms(a[:m]); R,rc=ms(a[m:])
res,c,i,j=[],0,0,0
while i<len(L) and j<len(R):
if L[i]<=R[j]: res.append(L[i]);i+=1
else: res.append(R[j]);j+=1;c+=len(L)-i
return res+L[i:]+R[j:],(lc+rc+c)
return ms(arr[:])[1]Inversion Count Complexity Summary
Summary: Brute force inversion count is O(n²). Modified merge sort achieves O(n log n) by counting cross-split inversions during the merge step. The additional cost is O(1) per comparison (adding len(left) - i), so the total overhead is O(n) per merge level — same as standard merge sort. Space is O(n) for the auxiliary arrays. This is the canonical example of using D&C to count order statistics in linearithmic time.
import time, random
def time_method(func, arr):
start = time.time()
result = func(arr[:])
return result, time.time() - start
def count_brute(arr):
return sum(1 for i in range(len(arr)) for j in range(i+1,len(arr)) if arr[i]>arr[j])
def count_dc(arr):
def ms(a):
if len(a)<=1: return a,0
m=len(a)//2;L,lc=ms(a[:m]);R,rc=ms(a[m:])
res,c,i,j=[],0,0,0
while i<len(L) and j<len(R):
if L[i]<=R[j]: res.append(L[i]);i+=1
else: res.append(R[j]);j+=1;c+=len(L)-i
return res+L[i:]+R[j:],(lc+rc+c)
return ms(arr[:])[1]
arr = random.sample(range(1000), 1000)
r1, t1 = time_method(count_brute, arr)
r2, t2 = time_method(count_dc, arr)
print(f'Brute: {r1} in {t1:.4f}s')
print(f'D&C: {r2} in {t2:.4f}s')
print(f'Speedup: {t1/t2:.1f}x')Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: inversions measure how unsorted an array is, with brute force O(n²) and D&C O(n log n), the modified merge sort counts cross-half inversions by adding len(left)-i each time a right element is chosen over a left element, and the correctness relies on the partition: left-left, right-right, and cross inversions are mutually exclusive and together cover all inversions. Next up we explore the Boyer-Moore voting algorithm for finding the majority element.
Frequently asked questions
Is the “Count Inversions Using Modified Merge Sort” lesson free?
Yes — the full text of “Count Inversions Using Modified Merge Sort” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Count Inversions Using Modified Merge Sort” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Divide and Conquer Template
- Count Inversions Using Modified Merge Sort
- Majority Element: Boyer-Moore Voting
- Median of Two Sorted Arrays