Introduction

An inversion in a permutation is a pair of positions that appear in the opposite order from the sorted sequence. Counting inversions is a standard way to measure how far a sequence is from sorted order, and it shows up in sorting analysis, ranking systems, and combinatorics.

What an Inversion Is

For a permutation p, an inversion is a pair of indices (i, j) such that:

• 'i < j'
• 'p[i] > p[j]'

Example:

For [2, 3, 1], the inversions are:

• '(0, 2) because 2 > 1'
• '(1, 2) because 3 > 1'

So the inversion count is 2.

If the permutation is already sorted, the inversion count is 0. If it is in reverse order, the inversion count is as large as possible.

Brute-Force Method

The direct solution checks every pair:

1def count_inversions_bruteforce(arr):
2    count = 0
3    for i in range(len(arr)):
4        for j in range(i + 1, len(arr)):
5            if arr[i] > arr[j]:
6                count += 1
7    return count
8
9
10print(count_inversions_bruteforce([2, 3, 1]))

This is easy to understand, but it runs in O(n^2) time because it checks all pairs.

That is fine for small arrays, but not for large ones.

Efficient O(n log n) Method

The standard optimized approach uses merge sort. The key observation is that when you merge two sorted halves, you can count many inversions at once.

Suppose:

• left half is sorted
• right half is sorted
• you compare left[i] and right[j]

If left[i] <= right[j], there is no new inversion involving left[i].

If left[i] > right[j], then right[j] is smaller than every remaining element in the left half. That contributes:

len(left) - i

new inversions in one step.

Merge-Sort Counting Code

1def count_inversions(arr):
2    def sort_and_count(nums):
3        if len(nums) <= 1:
4            return nums, 0
5
6        mid = len(nums) // 2
7        left, left_count = sort_and_count(nums[:mid])
8        right, right_count = sort_and_count(nums[mid:])
9
10        merged = []
11        i = j = 0
12        split_count = 0
13
14        while i < len(left) and j < len(right):
15            if left[i] <= right[j]:
16                merged.append(left[i])
17                i += 1
18            else:
19                merged.append(right[j])
20                split_count += len(left) - i
21                j += 1
22
23        merged.extend(left[i:])
24        merged.extend(right[j:])
25
26        return merged, left_count + right_count + split_count
27
28    return sort_and_count(arr)[1]
29
30
31print(count_inversions([2, 3, 1]))
32print(count_inversions([4, 1, 3, 2]))

This runs in O(n log n) time because it uses merge sort's divide-and-conquer structure.

Why the Merge Step Works

The merge step is where the efficiency comes from. Imagine:

• left = [4, 5, 7]
• right = [1, 6]

When you compare 4 and 1, you know 1 is smaller than 4, 5, and 7. So you immediately add 3 inversions instead of checking those pairs individually.

That is the whole trick. Sorting the halves makes it possible to count blocks of inversions instead of one pair at a time.

Permutations Versus General Arrays

The term "inversion" is usually introduced for permutations, but the counting algorithm works for any numeric array. The only difference is how duplicates are treated.

For strict inversion counting, equal values do not count as inversions. That is why the comparison in the merge step uses <= on the left side and only counts when left[i] > right[j].

Why Inversion Count Matters

Inversion count is useful because it gives a precise measure of disorder:

• insertion sort performs one swap-like correction per inversion
• ranking comparisons often use inversion-like distance measures
• reverse-ordered input produces the maximum inversion count

For a permutation of size n, the maximum number of inversions is:

n(n - 1) / 2

which happens when the permutation is completely reversed.

Common Pitfalls

The biggest mistake is using the brute-force method on large arrays and then wondering why performance collapses. The merge-sort method is the standard scalable solution.

Another mistake is counting equal values as inversions. An inversion requires a strict greater-than relation.

People also sometimes forget that the merge-sort method returns both a sorted array and a count. If you mutate the merging logic carelessly, you can break the correctness of the count.

Finally, do not confuse inversion count with the number of adjacent swaps already present. The inversion count tells you how many pairwise order violations exist.

Summary

• An inversion is a pair of indices in the wrong relative order.
• The brute-force counting method is O(n^2).
• The standard efficient method uses merge sort and runs in O(n log n).
• The merge step counts blocks of inversions whenever a right-side value jumps ahead of remaining left-side values.
• Equal values are not inversions unless your problem defines them that way explicitly.