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.

Practice

1. What does the term inversion in an array mean?

easy

A. A pair of elements where the first is smaller than the second and appears before it

B. A pair of elements where the first is greater than the second and appears before it

C. The total number of elements in the array

D. The sum of all elements in the array

Solution

1. Step 1: Understand the definition of inversion

   An inversion is when a larger number appears before a smaller number in the array.

2. Step 2: Compare options with definition

   A pair of elements where the first is greater than the second and appears before it correctly describes this pair condition, others do not.

3. Final Answer:

   A pair of elements where the first is greater than the second and appears before it -> Option B

4. Quick Check:

   Inversion = larger before smaller [OK]

Hint: Inversion means bigger number comes before smaller one [OK]

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts equal elements
• Mixing up element positions

2. Which of the following Python code snippets correctly counts inversions using a simple nested loop?

easy

A. count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1

B. count = 0
for i in range(len(arr)):
for j in range(i):
if arr[i] > arr[j]:
count += 1

C. count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] < arr[j]:
count += 1

D. count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] == arr[j]:
count += 1

Solution

1. Step 1: Check the loop ranges and condition

   count = 0 for i in range(len(arr)): for j in range(i+1, len(arr)): if arr[i] > arr[j]: count += 1 loops i from 0 to end and j from i+1 to end, comparing arr[i] > arr[j]. This matches inversion definition.

2. Step 2: Verify other options

   count = 0 for i in range(len(arr)): for j in range(i): if arr[i] > arr[j]: count += 1 checks arr[i] > arr[j] but loops j before i, counting later > earlier which is incorrect. count = 0 for i in range(len(arr)): for j in range(i+1, len(arr)): if arr[i] < arr[j]: count += 1 counts when arr[i] < arr[j], which is not inversion. count = 0 for i in range(len(arr)): for j in range(i+1, len(arr)): if arr[i] == arr[j]: count += 1 counts equal elements, not inversions.

3. Final Answer:

   count = 0 for i in range(len(arr)): for j in range(i+1, len(arr)): if arr[i] > arr[j]: count += 1 -> Option A

4. Quick Check:

   Nested loops with arr[i] > arr[j] count inversions [OK]

Hint: Use nested loops with j > i and check arr[i] > arr[j] [OK]

Common Mistakes:

• Checking arr[i] < arr[j] instead of >
• Looping j before i
• Counting equal elements as inversions

3. What is the output of the following code?

def count_inversions(arr):
    count = 0
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] > arr[j]:
                count += 1
    return count

print(count_inversions([2, 4, 1, 3, 5]))

medium

A. 5

B. 4

C. 2

D. 3

Solution

1. Step 1: Identify all inversion pairs in the array

   Array: [2, 4, 1, 3, 5]. Inversions are (2,1), (4,1), (4,3). Total 3 inversions.

2. Step 2: Confirm code counts these correctly

   Code loops through pairs and increments count for each inversion found, so returns 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Count inversions in [2,4,1,3,5] = 3 [OK]

Hint: Count pairs where earlier number is bigger [OK]

Common Mistakes:

• Missing some inversion pairs
• Counting pairs with equal elements
• Confusing order of pairs

4. Find the error in this code snippet for counting inversions:

def count_inversions(arr):
    count = 0
    for i in range(len(arr)):
        for j in range(i):
            if arr[i] > arr[j]:
                count += 1
    return count

print(count_inversions([3, 1, 2]))

medium

A. The inner loop should start from i+1, not 0 to i

B. The count variable is not initialized

C. The comparison should be arr[i] < arr[j] instead of arr[i] > arr[j]

D. The function does not return any value

Solution

1. Step 1: Analyze loop ranges and comparison

   Inner loop runs j from 0 to i-1, so j < i. The code checks if arr[i] > arr[j], counting pairs where later element is bigger.

2. Step 2: Identify correct inversion condition

   Inversion means earlier element is bigger than later one, so condition should be arr[j] > arr[i]. Current condition is reversed, causing wrong count.

3. Final Answer:

   The comparison should be arr[i] < arr[j] instead of arr[i] > arr[j] -> Option C

4. Quick Check:

   Inversion needs earlier > later, fix comparison [OK]

Hint: Check if earlier element is greater, not later [OK]

Common Mistakes:

• Reversing comparison operator
• Wrong loop ranges causing missed pairs
• Not returning count

5. Given the array [8, 4, 2, 1], what is the number of inversions? Also, explain why this count represents the worst case for inversion counting algorithms.

hard

A. 6; because the array is sorted in descending order, all pairs are inversions

B. 4; because only adjacent pairs are inversions

C. 0; because the array is sorted ascending

D. 3; because only some pairs are inversions

Solution

1. Step 1: Count all inversion pairs in the array

   Array: [8, 4, 2, 1]. Inversions: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1) = 6 total.

2. Step 2: Explain why this is worst case

   Array sorted descending means every pair is inverted. Algorithms checking pairs must count all, causing maximum work.

3. Final Answer:

   6; because the array is sorted in descending order, all pairs are inversions -> Option A

4. Quick Check:

   Descending array has max inversions = n(n-1)/2 [OK]

Hint: Descending order array has max inversions n(n-1)/2 [OK]

Common Mistakes:

• Counting only adjacent pairs
• Confusing ascending with descending
• Not recognizing worst case scenario