Counting Inversions in an Array

Approach — merge sort with a counter. During the merge of two sorted halves, when an element from the right half is emitted ahead of $k$ remaining elements in the left half, those $k$ elements each form an inversion with it. Accumulate as you merge.

def count_inversions(a):
    def sort_count(xs):
        if len(xs) <= 1:
            return xs, 0
        mid = len(xs) // 2
        left, cl = sort_count(xs[:mid])
        right, cr = sort_count(xs[mid:])
        merged, cm = [], 0
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i]); i += 1
            else:
                merged.append(right[j]); j += 1
                cm += len(left) - i      # all remaining left elems invert
        merged += left[i:] + right[j:]
        return merged, cl + cr + cm
    return sort_count(a)[1]

Recurrence $T(n) = 2T(n/2) + O(n)$ gives $O(n \log n)$ time and $O(n)$ space.

Alternative. Compress values to ranks and sweep right-to-left with a Binary Indexed Tree, querying the count of already-seen smaller values. Same complexity, often preferred when the array is streaming.

The statistical connection — this is the real question. The inversion count $I$ is exactly the unnormalised version of Kendall's tau:

So an $O(n\log n)$ inversion counter is an $O(n\log n)$ rank-correlation estimator. That matters in practice because Kendall's tau is robust to outliers and monotone transformations in a way Pearson correlation is not — which is why it shows up when scoring a signal against forward returns on heavy-tailed data.

Edge cases to mention: ties (decide $\le$ vs $<$ and stay consistent; ties need the tau-b correction), and overflow — $I$ can reach $\binom{n}{2}$, so use 64-bit.