Count Inversions in Array in DSA C - 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, and split inversions

↓

Return total inversions

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

Execution Sample

DSA C

int merge(int arr[], int temp[], int left, int mid, int right) {
  int i = left, j = mid, k = left, inv_count = 0;
  while (i <= mid - 1 && j <= right) {
    if (arr[i] <= arr[j]) temp[k++] = arr[i++];
    else {
      temp[k++] = arr[j++];
      inv_count += (mid - i);
    }
  }
  while (i <= mid - 1) temp[k++] = arr[i++];
  while (j <= right) temp[k++] = arr[j++];
  for (i = left; i <= right; i++) arr[i] = temp[i];
  return inv_count;
}

int mergeSort(int arr[], int temp[], int left, int right) {
  int mid, inv_count = 0;
  if (right > left) {
    mid = (left + right) / 2;
    inv_count += mergeSort(arr, temp, left, mid);
    inv_count += mergeSort(arr, temp, mid + 1, right);
    inv_count += merge(arr, temp, left, mid + 1, right);
  }
  return inv_count;
}

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

Execution Table

Step	Operation	Indices Involved	Inversions Counted	Array State	Temp Array State
1	Divide array	[0..4]	0	[2, 4, 1, 3, 5]	[]
2	Divide left half	[0..2]	0	[2, 4, 1, 3, 5]	[]
3	Divide left-left half	[0..1]	0	[2, 4, 1, 3, 5]	[]
4	Divide left-left-left half	[0..0]	0	[2, 4, 1, 3, 5]	[]
5	Divide left-left-right half	[1..1]	0	[2, 4, 1, 3, 5]	[]
6	Merge [0..0] and [1..1]	[0,1]	0	[2,4,1,3,5]	[2,4]
7	Divide left-right half	[2..2]	0	[2,4,1,3,5]	[]
8	Merge [0..1] and [2..2]	[0..2]	2	[1,2,4,3,5]	[1,2,4]
9	Divide right half	[3..4]	0	[1,2,4,3,5]	[]
10	Divide right-left half	[3..3]	0	[1,2,4,3,5]	[]
11	Divide right-right half	[4..4]	0	[1,2,4,3,5]	[]
12	Merge [3..3] and [4..4]	[3,4]	0	[1,2,4,3,5]	[3,5]
13	Merge [0..2] and [3..4]	[0..4]	1	[1,2,3,4,5]	[1,2,3,4,5]
14	Total inversions	All	3	[1,2,3,4,5]	[1,2,3,4,5]

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

Variable Tracker

Variable	Start	After Step 6	After Step 8	After Step 12	After Step 13	Final
inv_count	0	0	2	2	3	3
arr	[2,4,1,3,5]	[2,4,1,3,5]	[1,2,4,3,5]	[1,2,4,3,5]	[1,2,3,4,5]	[1,2,3,4,5]
temp	[]	[2,4]	[1,2,4]	[3,5]	[1,2,3,4,5]	[1,2,3,4,5]

Key Moments - 3 Insights

Why do we add (mid - i) to inversion count when arr[i] > arr[j] during merge?

Because arr[i] and all elements from i to mid-1 are greater than arr[j], so each forms an inversion. See step 8 where 2 inversions are counted.

Why do we copy elements back from temp to arr after merging?

To keep arr sorted for the next merge step. Without copying back, next merges would use unsorted data. See step 13 where arr is updated.

Why do we divide the array until single elements before merging?

Because single elements are trivially sorted, merging them step-by-step counts inversions correctly. See steps 4 and 5 where base cases occur.

Visual Quiz - 3 Questions

Look at the execution_table, what is the inversion count after merging indices [0..2]?

A 0

B 4

C 2

D 1

💡 Hint

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

At which step does the array become fully sorted?

A Step 13

B Step 8

C Step 12

D Step 14

💡 Hint

Look at the 'Array State' column; full sorted array appears at step 13.

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

A It would be 2

B It would be 0

C It would be 4

D It would be equal to array length

💡 Hint

Inversion count increases only when arr[i] > arr[j], see step 8 where inversions are counted.

Concept Snapshot

Count Inversions in Array:
- Use divide and conquer (merge sort) approach
- Recursively split array until single elements
- Merge halves counting pairs where left > right
- Sum counts from left, right, and merge steps
- Result is total number of inversions in array

Full Transcript

Counting inversions means finding how many pairs in an array are out of order. We use a method like merge sort: split the array into halves until single elements remain, then merge them back while counting how many elements from the left half are greater than those in the right half. Each such pair is an inversion. We add counts from left half, right half, and the merge step to get the total. The execution table shows how the array is divided, merged, and how inversion counts accumulate step-by-step. Key points include why we add (mid - i) during merge when an element from the right half is smaller, and why we copy back the merged array. This method efficiently counts inversions in O(n log n) time.

Practice

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

easy

A. The total number of elements in the array

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

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

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 matches this definition exactly, others describe different concepts.

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 inversion with total pairs

2. Which of the following C code snippets correctly declares a function to count inversions in an array?

easy

A. int countInversions(int arr[], int n);

B. void countInversions(int arr[], int n);

C. int countInversions(int arr, int n[]);

D. int countInversions(int *arr, int n[]);

Solution

1. Step 1: Check function signature correctness

   The function should return an integer count and take an integer array and its size as parameters.

2. Step 2: Analyze each option

   int countInversions(int arr[], int n); correctly uses int return type and parameters as int arr[] and int n. Others have wrong parameter types or return type.

3. Final Answer:

   int countInversions(int arr[], int n); -> Option A

4. Quick Check:

   Correct function signature returns int and takes int array and size [OK]

Hint: Function returns int and takes int array plus size [OK]

Common Mistakes:

• Using void return type instead of int
• Swapping array and size parameter types
• Using pointer syntax incorrectly

3. What is the output of the following C code snippet?

int arr[] = {2, 4, 1, 3, 5};
int n = 5;
int count = 0;
for(int i = 0; i < n-1; i++) {
  for(int j = i+1; j < n; j++) {
    if(arr[i] > arr[j]) count++;
  }
}
printf("%d", count);

medium

A. 5

B. 4

C. 3

D. 2

Solution

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

   Pairs where first element is greater than second: (2,1), (4,1), (4,3). Total = 3.

2. Step 2: Confirm count variable increments correctly

   Nested loops check all pairs; count increments for each inversion found, total 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Inversions = 3 [OK]

Hint: Count pairs where left element > right element [OK]

Common Mistakes:

• Counting pairs where left < right
• Missing some inversion pairs
• Off-by-one errors in loops

4. The following code is intended to count inversions but has a bug. What is the bug?

int countInversions(int arr[], int n) {
  int count = 0;
  for(int i = 0; i < n; i++) {
    for(int j = i; j < n; j++) {
      if(arr[i] >= arr[j]) count++;
    }
  }
  return count;
}

medium

A. Inner loop should start from j = i + 1, not j = i

B. The count variable should be initialized outside the function

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

D. The function should return void instead of int

Solution

1. Step 1: Analyze loop ranges for counting pairs

   Inner loop starts at j = i, so it compares arr[i] with itself, causing incorrect counting.

2. Step 2: Correct inner loop start index

   Inner loop should start at j = i + 1 to avoid self-comparison.

3. Final Answer:

   Inner loop should start from j = i + 1, not j = i -> Option A

4. Quick Check:

   Start inner loop at i+1 to avoid self-comparison [OK]

Hint: Inner loop must start after outer loop index [OK]

Common Mistakes:

• Starting inner loop at same index as outer
• Wrong comparison operator
• Returning wrong type

5. Given the array {8, 4, 2, 1}, what is the total number of inversions? Also, explain why this number represents the worst case for inversion counting.

hard

A. 4

B. 0

C. 3

D. 6

Solution

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

   Pairs: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1) total 6 inversions.

2. Step 2: Understand why this is worst case

   The array is sorted in descending order, so every pair is inverted, maximum inversions possible for size 4.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Descending order 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 inversions
• Forgetting pairs with elements far apart
• Confusing inversion count with array length