Count Inversions in Array in DSA C#

Mental Model

Count how many pairs of numbers are out of order in an array. Each pair where a bigger number comes before a smaller one is an inversion.

Analogy: Imagine a line of people waiting by height. Every time a taller person stands before a shorter one, it's like an inversion. Counting all these pairs tells us how mixed up the line is.

Array: [2, 4, 1, 3, 5]
Inversions: (2,1), (4,1), (4,3)
Visual:
2 -> 4 -> 1 -> 3 -> 5
 ↑         ↑
 bigger    smaller
 but comes before

Dry Run Walkthrough

Input: array: [2, 4, 1, 3, 5]

Goal: Count all pairs where a bigger number appears before a smaller number

Step 1: Split array into two halves: left=[2,4,1], right=[3,5]

Left: 2 -> 4 -> 1
Right: 3 -> 5

Why: Divide to conquer: counting inversions is easier when arrays are smaller and sorted

Step 2: Split left half again: left_left=[2,4], left_right=[1]

Left_Left: 2 -> 4
Left_Right: 1

Why: Keep dividing until subarrays have one element

Step 3: Split left_left into [2] and [4], both single elements

2
4

Why: Single elements have zero inversions

Step 4: Merge [2] and [4] back sorted: [2,4], count inversions=0

2 -> 4

Why: No inversion because 2 < 4

Step 5: Merge [2,4] and [1], count inversions where left element > right element

Merging 2 -> 4 and 1
Inversions found: (2,1), (4,1)
Merged: 1 -> 2 -> 4

Why: 1 is smaller than both 2 and 4, so two inversions

Step 6: Right half [3,5] split into [3] and [5], merge sorted with 0 inversions

3 -> 5

Why: Already sorted, no inversions

Step 7: Merge left [1,2,4] and right [3,5], count inversions

Compare 1 and 3 (no inversion), 2 and 3 (no inversion), 4 and 3 (inversion)
Merged: 1 -> 2 -> 3 -> 4 -> 5

Why: 4 > 3 is one inversion

Result:

Final sorted array: 1 -> 2 -> 3 -> 4 -> 5
Total inversions: 3

Annotated Code

DSA C#

using System;

class CountInversions {
    // Merge two sorted halves and count inversions
    static int Merge(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left; // start of left half
        int j = mid + 1; // start of right half
        int k = left; // start of temp array
        int invCount = 0;

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++]; // take from left
            } else {
                temp[k++] = arr[j++]; // take from right
                invCount += (mid - i + 1); // count inversions
            }
        }

        while (i <= mid) temp[k++] = arr[i++]; // copy remaining left
        while (j <= right) temp[k++] = arr[j++]; // copy remaining right

        for (int idx = left; idx <= right; idx++) arr[idx] = temp[idx]; // copy back
        return invCount;
    }

    // Recursive merge sort that counts inversions
    static int MergeSort(int[] arr, int[] temp, int left, int right) {
        int invCount = 0;
        if (left < right) {
            int mid = (left + right) / 2;
            invCount += MergeSort(arr, temp, left, mid); // left half
            invCount += MergeSort(arr, temp, mid + 1, right); // right half
            invCount += Merge(arr, temp, left, mid, right); // merge and count
        }
        return invCount;
    }

    static void Main() {
        int[] arr = {2, 4, 1, 3, 5};
        int[] temp = new int[arr.Length];
        int result = MergeSort(arr, temp, 0, arr.Length - 1);
        Console.WriteLine("Sorted array: " + string.Join(" -> ", arr));
        Console.WriteLine("Total inversions: " + result);
    }
}

if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; invCount += (mid - i + 1); }

Compare elements from left and right halves; count inversions when left element is bigger

invCount += MergeSort(arr, temp, left, mid); invCount += MergeSort(arr, temp, mid + 1, right); invCount += Merge(arr, temp, left, mid, right);

Recursively sort left and right halves and merge counting inversions

Output

Sorted array: 1 -> 2 -> 3 -> 4 -> 5

Total inversions: 3

Complexity Analysis

Time: O(n log n) because the array is divided and merged log n times, each merge takes O(n)

Space: O(n) due to temporary array used for merging

vs Alternative: Naive approach is O(n^2) by checking all pairs; merge sort method is much faster for large arrays

Edge Cases

Empty array

Returns 0 inversions without error

DSA C#

if (left < right) { ... }

Array with one element

Returns 0 inversions since no pairs exist

DSA C#

if (left < right) { ... }

Array with all equal elements

Returns 0 inversions because no element is greater than another

DSA C#

if (arr[i] <= arr[j]) { ... }

When to Use This Pattern

When asked to count how many pairs are out of order in an array, use the merge sort inversion counting pattern because it efficiently counts while sorting.

Common Mistakes

Mistake: Counting inversions only when arr[i] > arr[j] but forgetting to add the number of remaining elements in left half
Fix: Add (mid - i + 1) to inversion count when taking element from right half during merge

Mistake: Not copying merged elements back to original array after merge
Fix: Copy temp array back to arr after merging to keep array sorted for next steps

Summary

Counts how many pairs in an array are out of order using a modified merge sort.

Use it when you need to find how mixed up an array is efficiently.

The key insight is counting inversions during the merge step by knowing how many elements remain in the left half.

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