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.