Inversion Counting — Disorder in Rankings

An inversion is a pair (i,j) with i < j but a[i] > a[j]. Counting inversions measures how far an array is from sorted—useful in rankings, collaborative filtering, and as a merge sort subroutine.

Why this shows up in the real world

Music charts sometimes compare user preference lists to a canonical ranking; inversion distance quantifies disagreement. E‑commerce “recommended for you” may rank co-purchases—measuring inversions between two engines’ lists spots drift. Version control merge tools implicitly reason about ordering conflicts; inversion counting is a clean numeric lens on disorder.

Core idea (explained for students)

Naive O(n²) double loop works for teaching tiny inputs. The contest-grade approach uses merge sort: when merging left and right halves, if L[i] <= R[j] take from left; else every remaining element in L forms an inversion with R[j], so add len(L)-i to the answer. This runs in O(n log n). The same structure appears in “reverse pairs” problems on LeetCode.

Try this in Python

def merge_count(a):
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left, cl = merge_count(a[:mid])
    right, cr = merge_count(a[mid:])
    merged, cm = merge(left, right)
    return merged, cl + cr + cm


def merge(left, right):
    i = j = inv = 0
    out = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            inv += len(left) - i
            out.append(right[j])
            j += 1
    return out + left[i:] + right[j:], inv


arr, k = merge_count([2, 4, 1, 3, 5])
print(k, arr)

Common mistakes

• Integer overflow in inversion counts—use Python ints or mod.
• Off-by-one when adding len(left)-i during merge.
• Double counting when duplicates exist—define ties carefully (strict > vs >=).

Key takeaways

• Inversions = Kendall tau distance flavor for permutations.
• Merge-based counting is the standard O(n log n) trick.
• Tie-handling changes the count—match problem statement.