Count Inversions in Array in DSA C# - Execution Trace

Concept Flow - Count Inversions in Array

Start with array

↓

Split array into halves

↓

Recursively count inversions in left half

↓

Recursively count inversions in right half

↓

Merge two halves while counting cross inversions

↓

Sum left + right + cross inversions

↓

Return total inversions

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

Execution Sample

DSA C#

int CountInversions(int[] arr, int left, int right) {
  if (left >= right) return 0;
  int mid = (left + right) / 2;
  int leftInv = CountInversions(arr, left, mid);
  int rightInv = CountInversions(arr, mid + 1, right);
  int crossInv = MergeAndCount(arr, left, mid, right);
  return leftInv + rightInv + crossInv;
}

This code counts inversions by recursively splitting and merging the array, counting inversions during merge.

Execution Table

Step	Operation	Subarray Processed	Inversions Counted	Array State
1	Split full array	[2, 4, 1, 3, 5]	0	[2, 4, 1, 3, 5]
2	Split left half	[2, 4, 1]	0	[2, 4, 1, 3, 5]
3	Split left-left half	[2, 4]	0	[2, 4, 1, 3, 5]
4	Split left-left-left half	[2]	0	[2, 4, 1, 3, 5]
5	Split left-left-right half	[4]	0	[2, 4, 1, 3, 5]
6	Merge [2] and [4]	[2, 4]	0	[2, 4, 1, 3, 5]
7	Split left-right half	[1]	0	[2, 4, 1, 3, 5]
8	Merge [2,4] and [1]	[2, 4, 1]	2	[1, 2, 4, 3, 5]
9	Split right half	[3, 5]	0	[1, 2, 4, 3, 5]
10	Split right-left half	[3]	0	[1, 2, 4, 3, 5]
11	Split right-right half	[5]	0	[1, 2, 4, 3, 5]
12	Merge [3] and [5]	[3, 5]	0	[1, 2, 4, 3, 5]
13	Merge [1, 2, 4] and [3, 5]	[1, 2, 4, 3, 5]	1	[1, 2, 3, 4, 5]
14	Total inversions	[Full array]	3	[1, 2, 3, 4, 5]

💡 All subarrays processed and merged, total inversions counted as 3.

Variable Tracker

Variable	Start	After Step 6	After Step 8	After Step 12	After Step 13	Final
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]
leftInv	0	0	2	0	0	2 (step 8) + 0 (step 12) + 1 (step 13) = 3
rightInv	0	0	0	0	0	0
crossInv	0	0	0	0	1	0

Key Moments - 3 Insights

Why do we count inversions during the merge step and not just when splitting?

Because inversions can be between elements in different halves, which are only detected when merging sorted halves (see steps 8 and 13 in execution_table).

Why does the array get sorted during inversion counting?

The merge step sorts the array while counting cross inversions, so the array state changes after merges (see array state changes at steps 8 and 13).

How do we know when to stop splitting the array?

When the subarray has one or zero elements (base case), no inversions exist there (see steps 4,5,7,10,11).

Visual Quiz - 3 Questions

Look at the execution_table, how many inversions are counted during merging [2,4] and [1] at step 8?

A 1

B 2

C 0

D 3

💡 Hint

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

At which step does the array become fully sorted?

A Step 8

B Step 6

C Step 13

D Step 14

💡 Hint

Look at the 'Array State' column and find when the array is [1, 2, 3, 4, 5].

If the input array was already sorted, how would the 'Inversions Counted' values change in the execution_table?

A All would be zero

B They would increase

C Only cross inversions would be counted

D Only left half inversions would be counted

💡 Hint

Inversions count pairs where earlier element is greater than later; sorted array has none.

Concept Snapshot

Count Inversions in Array:
- Use divide and conquer (merge sort) approach
- Recursively split array until single elements
- Count inversions in left, right, and during merge
- Merge step counts cross inversions and sorts
- Total inversions = left + right + cross
- Runs in O(n log n) time

Full Transcript

Counting inversions in an array means finding how many pairs of elements are out of order. We use a divide and conquer method similar to merge sort. The array is split into halves recursively until single elements remain. Then, during merging, we count how many elements from the right half come before elements from the left half, which are cross inversions. We add these counts to the inversions found in the left and right halves. The array gets sorted as a side effect. This method efficiently counts inversions in O(n log n) time, much faster than checking all pairs.

Practice

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

easy

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

B. A pair of elements where the first is smaller 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 a pair of elements (i, j) such that i < j but array[i] > array[j].

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 condition, while others describe unrelated concepts.

3. Final Answer:

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

4. Quick Check:

   Inversion = pair (i, j) with i < j and array[i] > array[j] [OK]

Hint: Inversion means earlier bigger number than a later one [OK]

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts pairs where first is smaller
• Counting total elements instead of pairs

2. Which of the following C# code snippets correctly initializes an integer array named arr with values 3, 1, 2?

easy

A. int arr[] = new int[3] {3, 1, 2};

B. int arr = {3, 1, 2};

C. int[] arr = new int[] {3, 1, 2};

D. int arr[] = {3, 1, 2};

Solution

1. Step 1: Review C# array initialization syntax

   In C#, arrays must be declared as int[] arr and can be initialized explicitly with new int[] {values};

2. Step 2: Check each option

   int arr[] = new int[3] {3, 1, 2}; uses invalid declaration syntax (arr[]). int arr = {3, 1, 2}; tries to assign an array to an int. int arr[] = {3, 1, 2}; uses invalid declaration syntax (arr[]). int[] arr = new int[] {3, 1, 2}; uses the correct explicit syntax.

3. Final Answer:

   int[] arr = new int[] {3, 1, 2}; -> Option C

4. Quick Check:

   Correct array init uses new int[] {values} [OK]

Hint: Use new int[] { } to initialize arrays explicitly [OK]

Common Mistakes:

• Omitting new int[] in initialization
• Using C/C++ style array declaration
• Incorrect array size syntax

3. What is the output of the following C# code that counts inversions in the array arr = {2, 4, 1, 3, 5}?

int CountInversions(int[] arr) {
    int count = 0;
    for (int i = 0; i < arr.Length - 1; i++) {
        for (int j = i + 1; j < arr.Length; j++) {
            if (arr[i] > arr[j]) count++;
        }
    }
    return count;
}

int[] arr = {2, 4, 1, 3, 5};
Console.WriteLine(CountInversions(arr));

medium

A. 3

B. 4

C. 2

D. 5

Solution

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

   Pairs where first > second and first index < second index: (2,1), (4,1), (4,3) -> total 3 inversions.

2. Step 2: Confirm code counts these pairs

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

3. Final Answer:

   3 -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Counting pairs where first is smaller
• Missing some inversion pairs
• Off-by-one errors in loops

4. The following code attempts to count inversions but gives wrong output. What is the error?

int CountInversions(int[] arr) {
    int count = 0;
    for (int i = 0; i < arr.Length; i++) {
        for (int j = 0; j < arr.Length; j++) {
            if (arr[i] > arr[j]) count++;
        }
    }
    return count;
}

medium

A. The function should return void

B. Comparison should be arr[i] < arr[j]

C. Count variable should be initialized outside the function

D. Inner loop should start from i+1, not 0

Solution

1. Step 1: Analyze loop ranges for counting inversions

   Inversion pairs require i < j, but inner loop starts at 0, counting pairs twice and including invalid pairs.

2. Step 2: Fix inner loop start index

   Changing inner loop to start at i+1 ensures only pairs with i < j are counted once.

3. Final Answer:

   Inner loop should start from i+1, not 0 -> Option D

4. Quick Check:

   Count inversions need j > i, so inner loop from i+1 [OK]

Hint: Inner loop must start after outer index to avoid double count [OK]

Common Mistakes:

• Starting inner loop at 0 causing double counting
• Reversing comparison operator
• Misplacing count initialization

5. Given the array arr = {8, 4, 2, 1}, what is the total number of inversions? Use the efficient merge sort based method to count inversions.

hard

A. 7

B. 6

C. 4

D. 5

Solution

1. Step 1: Understand inversions in the array

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

2. Step 2: Count inversions using merge sort method

   Subarrays [8,4] and [2,1] each add 1 inversion (total 2). Final merge of [4,8] and [1,2]: +2 when taking 1, +2 when taking 2 (total 4). Grand total: 6.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Merge sort inversion count for {8,4,2,1} = 6 [OK]

Hint: Merge sort counts inversions during merge step [OK]

Common Mistakes:

• Counting only direct pairs, missing cross merges
• Using brute force count only
• Misunderstanding merge step inversion counting