Count Inversions in Array in DSA Python - Execution Trace

Concept Flow - Count Inversions in Array

Start with array

↓

Divide array into two halves

↓

Recursively count inversions in left half

↓

Recursively count inversions in right half

↓

Merge two halves while counting split inversions

↓

Sum left + right + split inversions

↓

Return total inversions

The array is split into halves recursively, counting inversions inside each half and across halves during merge, then sums all counts.

Execution Sample

DSA Python

def merge_count(arr, temp, left, right):
    if left >= right:
        return 0
    mid = (left + right) // 2
    inv = merge_count(arr, temp, left, mid)
    inv += merge_count(arr, temp, mid+1, right)
    i, j, k = left, mid+1, left
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]
            i += 1
        else:
            temp[k] = arr[j]
            inv += (mid - i + 1)
            j += 1
        k += 1
    while i <= mid:
        temp[k] = arr[i]
        i += 1
        k += 1
    while j <= right:
        temp[k] = arr[j]
        j += 1
        k += 1
    for idx in range(left, right+1):
        arr[idx] = temp[idx]
    return inv

This code counts inversions by recursively splitting and merging the array, counting how many pairs are out of order.

Execution Table

Step	Operation	Indices (left, mid, right)	Inversions Counted	Array State	Merge Visual
1	Split array	(0, 2, 4)	0	[2, 4, 1, 3, 5]	N/A
2	Split left half	(0, 1, 2)	0	[2, 4, 1, 3, 5]	N/A
3	Split left-left half	(0, 0, 1)	0	[2, 4, 1, 3, 5]	N/A
4	Split single elements	(0, 0, 0)	0	[2, 4, 1, 3, 5]	N/A
5	Split single elements	(1, 1, 1)	0	[2, 4, 1, 3, 5]	N/A
6	Merge (0,0,1)	left=0, mid=0, right=1	0	[2, 4, 1, 3, 5]	2 <= 4, no inversion
7	Split right half	(2, 3, 4)	0	[2, 4, 1, 3, 5]	N/A
8	Split right-left half	(2, 2, 3)	0	[2, 4, 1, 3, 5]	N/A
9	Split single elements	(2, 2, 2)	0	[2, 4, 1, 3, 5]	N/A
10	Split single elements	(3, 3, 3)	0	[2, 4, 1, 3, 5]	N/A
11	Merge (2,2,3)	left=2, mid=2, right=3	0	[2, 4, 1, 3, 5]	1 <= 3, no inversion
12	Split right-right half	(4, 4, 4)	0	[2, 4, 1, 3, 5]	N/A
13	Merge (2,3,4)	left=2, mid=3, right=4	0	[2, 4, 1, 3, 5]	3 <= 5, no inversion
14	Merge (0,2,4)	left=0, mid=2, right=4	3	[1, 2, 3, 4, 5]	2 > 1 (2 inversions), 4 > 3 (1 inversion)
15	End	N/A	3	[1, 2, 3, 4, 5]	Sorted array, total inversions = 3

💡 All subarrays merged and counted, final sorted array and total inversions returned.

Variable Tracker

Variable	Start	After Step 6	After Step 11	After Step 13	After Step 14	Final
arr	[2, 4, 1, 3, 5]	[2, 4, 1, 3, 5]	[2, 4, 1, 3, 5]	[2, 4, 1, 3, 5]	[1, 2, 3, 4, 5]	[1, 2, 3, 4, 5]
temp	[_, _, _, _, _]	[2, 4, _, _, _]	[2, 4, _, _, _]	[2, 4, 1, 3, _]	[1, 2, 3, 4, 5]	[1, 2, 3, 4, 5]
inversions	0	0	0	0	3	3
i	0	1	1	1	3	N/A
j	1	1	3	4	4	N/A
k	0	2	3	5	5	N/A

Key Moments - 3 Insights

Why do we count (mid - i + 1) inversions when arr[i] > arr[j] during merge?

Because arr[i] and all elements from i to mid are greater than arr[j], so each forms an inversion. See step 14 in execution_table where 2 > 1 counts 2 inversions.

Why do we merge sorted halves instead of counting inversions directly?

Merging sorted halves lets us count split inversions efficiently by comparing elements in order. This is shown in steps 6, 11, 13, and 14 where merging happens.

Why does the recursion stop when left >= right?

Because a single element or empty subarray has no inversions. This base case is shown in steps 4, 5, 9, 10, and 12.

Visual Quiz - 3 Questions

Look at the execution_table at step 14, how many inversions are counted during the merge?

A 3

B 2

C 1

D 0

💡 Hint

Check the 'Inversions Counted' column at step 14 in execution_table.

At which step does the array become fully sorted?

A Step 11

B Step 14

C Step 13

D Step 6

💡 Hint

Look at the 'Array State' column and find when it shows sorted [1, 2, 3, 4, 5].

If the array was already sorted, how would the inversion count change at step 14?

A It would be one

B It would be three

C It would be zero

D It would be negative

💡 Hint

Refer to how inversions are counted only when arr[i] > arr[j] during merge in execution_table step 14.

Concept Snapshot

Count Inversions in Array using Merge Sort:
- Split array recursively into halves
- Count inversions in left and right halves
- Count split inversions while merging sorted halves
- Sum all counts for total inversions
- Efficient O(n log n) method vs O(n^2) naive

Full Transcript

Counting inversions in an array means finding how many pairs are out of order. We use a merge sort approach: split the array into halves recursively, count inversions inside each half, then count inversions across halves while merging. During merge, when an element from the right half is smaller than one from the left, it forms inversions with all remaining elements in the left half. We sum these counts and return the total. This method sorts the array and counts inversions efficiently.