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 person, it counts as a mix-up or inversion.

Array: [2, 4, 1, 3, 5]
Indices:  0  1  2  3  4
Inversions: pairs like (2,1), (4,1), (4,3)

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 by counting inversions in smaller parts

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

left_left: [2,4]
left_right: [1]

Why: Keep splitting until subarrays have one element

Step 3: Count inversions in left_left by merging [2] and [4]

merged left_left: [2,4], inversions=0

Why: No inversion since 2 < 4

Step 4: Merge left_left [2,4] and left_right [1], count inversions

merged left: [1,2,4], inversions=2 (pairs: (2,1), (4,1))

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

Step 5: Count inversions in right half by merging [3] and [5]

merged right: [3,5], inversions=0

Why: No inversion since 3 < 5

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

merged full: [1,2,3,4,5], inversions=1 (pair: (4,3))

Why: 4 is before 3, so one inversion

Result:

Final merged array: [1,2,3,4,5]
Total inversions: 3

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Merge two sorted halves and count inversions
long long merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left;    // start of left subarray
    int j = mid + 1; // start of right subarray
    int k = left;    // start of temp array
    long long inv_count = 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
            inv_count += (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 to original
    }

    return inv_count;
}

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

int main() {
    int arr[] = {2, 4, 1, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int *temp = (int *)malloc(n * sizeof(int));
    long long result = mergeSort(arr, temp, 0, n - 1);
    free(temp);

    // Print sorted array
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i < n - 1) printf(" -> ");
    }
    printf(" -> null\n");

    // Print inversion count
    printf("Total inversions: %lld\n", result);
    return 0;
}

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

merge step: count inversions when right element is smaller than left

inv_count += mergeSort(arr, temp, left, mid); inv_count += mergeSort(arr, temp, mid + 1, right); inv_count += merge(arr, temp, left, mid, right);

divide array, count inversions in halves and merge step

Output

1 -> 2 -> 3 -> 4 -> 5 -> null

Total inversions: 3

Complexity Analysis

Time: O(n log n) because the array is repeatedly split and merged, counting inversions during merges

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) { ... } in mergeSort

array with one element

returns 0 inversions as no pairs exist

DSA C

if (left < right) { ... } in mergeSort

array with all equal elements

returns 0 inversions since no element is greater than another

DSA C

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

When to Use This Pattern

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

Common Mistakes

Mistake: Counting inversions only by comparing adjacent elements
Fix: Use merge step to count all cross inversions between halves, not just adjacent pairs

Mistake: Not copying merged elements back to original array
Fix: After merging, copy temp array back to original to keep array sorted for next merges

Summary

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

Use when you need to find how 'unsorted' an array is efficiently.

The key insight is counting inversions during the merge step of merge sort.