Why Count Inversions in Array in DSA C?

The Big Idea

What if you could count all the out-of-order pairs in a huge list without checking each pair one by one?

The Scenario

Imagine you have a list of numbers, and you want to know how many pairs are out of order. For example, in a list of students lined up by height, how many pairs are standing in the wrong order?

The Problem

Checking every pair manually means looking at each number and comparing it with all others after it. This takes a very long time if the list is big, and it's easy to make mistakes counting pairs.

The Solution

Using a smart method, we can count these out-of-order pairs quickly by splitting the list and counting while merging. This saves time and avoids errors.

Before vs After

✗ Before

int countInversions(int array[], int size) {
    int count = 0;
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (array[i] > array[j]) count++;
        }
    }
    return count;
}

✓ After

int mergeSortAndCount(int array[], int temp[], int left, int right) {
    int mid, count = 0;
    if (right > left) {
        mid = (right + left) / 2;
        count += mergeSortAndCount(array, temp, left, mid);
        count += mergeSortAndCount(array, temp, mid + 1, right);
        count += merge(array, temp, left, mid, right);
    }
    return count;
}

What It Enables

This method lets us quickly find how many pairs are out of order in large lists, making sorting and analysis much faster.

Real Life Example

In a race, counting how many runners are ahead of faster runners helps understand how mixed up the starting positions are.

Key Takeaways

Manual counting is slow and error-prone for large lists.

Divide and conquer approach counts inversions efficiently.

Useful for analyzing order and sorting problems.