Merge Sort / Inversion Count

Merge Sort for Counting Inversions

An inversion in an array is a pair of indices (i, j) where i < j but nums[i] > nums[j], an element that appears earlier but is larger than a later element. Counting inversions measures how "unsorted" an array is: a fully sorted array has zero inversions, and a fully reversed array has the maximum possible, n*(n-1)/2.

The naive approach checks every pair in $O(n²)$. For competitive programming and interview problems, that's too slow. The elegant solution reuses merge sort's divide-and-conquer structure to count inversions in $O(n \log n)$.

Why Merge Sort Works

The key observation is that merge sort already does the work of comparing elements across different positions. It's just normally discarding a piece of information we care about. During the merge step, when we have two sorted halves and we're interleaving them, we can detect cross-half inversions for free.

Here's the insight: suppose the left half is [1, 3, 5] and the right half is [2, 4, 6], and we're merging. When we compare left[i] = 3 with right[j] = 2 and find that left[i] > right[j], we know that right[j] = 2 is smaller than 3 and every element that comes after 3 in the left half, that is, 5 as well. Both halves are already sorted, so left[i], left[i+1], ..., left[-1] are all greater than right[j]. That's len(left) - i inversions discovered in a single step.

Inversions within each half are handled recursively. Inversions that cross the midpoint, one index in the left half and one in the right, are counted during the merge. Since every inversion falls into exactly one of these two categories, the count is exact.

Walked Example: [2, 4, 1, 3, 5]

The inversions in this array are (2,1), (4,1), (4,3): three pairs where a larger number appears before a smaller one. Let's trace how merge sort finds them.

Split into [2, 4] and [1, 3, 5]. Each half is recursively sorted and counted (both are already sorted, so zero inversions within each). Now merge:

• Compare left[0]=2 vs right[0]=1. Since 2 > 1, we take from the right and add len(left) - 0 = 2 inversions (both 2 and 4 are greater than 1).
• Compare left[0]=2 vs right[1]=3. Since 2 <= 3, take from the left. No inversions.
• Compare left[1]=4 vs right[1]=3. Since 4 > 3, take from the right and add len(left) - 1 = 1 inversion (only 4 remains on the left).
• Remaining left element 4 is appended. No further inversions.

Total cross-half inversions: 2 + 1 = 3. Combined with the zero within each half: 3 total inversions. Correct.

The Code

def count_inversions(nums):
    if len(nums) <= 1:
        return nums, 0

    mid = len(nums) // 2
    left, l_cnt = count_inversions(nums[:mid])
    right, r_cnt = count_inversions(nums[mid:])

    merged = []
    cnt = l_cnt + r_cnt
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:   # note: <= not <
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            cnt += len(left) - i  # all of left[i:] > right[j]
            j += 1

    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, cnt

Why <= Matters

The comparison left[i] <= right[j] (not strict <) is important for correctness. An inversion requires a strictly greater element appearing earlier, so equal elements are not inversions. If we used < and moved from the right when elements are equal, we'd incorrectly count pairs of equal values as inversions. The <= choice keeps the sort stable (equal elements from the left half stay before those from the right half) and keeps the count accurate.

Reverse Pairs Variant

LeetCode 493. Reverse Pairs asks for pairs where nums[i] > 2 * nums[j] with i < j. This is trickier because the condition isn't a simple comparison that doubles as a merge decision. The standard approach separates counting from merging: before merging, use a two-pointer pass over the two sorted halves to count qualifying pairs, then perform the normal merge afterward.

def reverse_pairs(nums):
    def merge_count(arr):
        if len(arr) <= 1:
            return arr, 0
        mid = len(arr) // 2
        left, l_cnt = merge_count(arr[:mid])
        right, r_cnt = merge_count(arr[mid:])

        # Count reverse pairs with a two-pointer sweep (before merging)
        cnt = l_cnt + r_cnt
        j = 0
        for val in left:
            while j < len(right) and val > 2 * right[j]:
                j += 1
            cnt += j

        # Normal merge
        merged, i, k = [], 0, 0
        while i < len(left) and k < len(right):
            if left[i] <= right[k]:
                merged.append(left[i]); i += 1
            else:
                merged.append(right[k]); k += 1
        merged.extend(left[i:])
        merged.extend(right[k:])
        return merged, cnt

    _, total = merge_count(nums)
    return total

The key is that the two-pointer counting pass is valid because both halves are already sorted at that point: as val increases across the left half, the threshold j never needs to move backwards, giving an $O(n)$ pass per merge level.

Count Smaller After Self

The problem LeetCode 315. Count of Smaller Numbers After Self asks for an array counts where counts[i] is the number of elements to the right of i that are smaller than nums[i]. Merge sort handles this by tracking original indices through the sort. When a right-half element is placed before left-half elements during a merge, each skipped left-half element gains one count. Maintaining an array of (value, original_index) pairs and updating a result array during the merge is the standard approach, following the same $O(n \log n)$ structure.

Complexity

Time complexity is $O(n \log n)$: the recurrence T(n) = 2T(n/2) + $O(n)$ is the same as standard merge sort, with the counting work folded into the $O(n)$ merge step. Space complexity is $O(n)$ for the auxiliary arrays created during merging. This is a genuine improvement over the $O(n²)$ brute force for large inputs, and the constant factors are small since the merge step is cache-friendly sequential access.

Recognizing this pattern

You're probably looking at merge sort + inversion counting when:

• You need to count pairs (i, j) with i < j satisfying some relation between nums[i] and nums[j].
• Brute force is $O(n^2)$ but n is up to $10^5$ or more.
• The relation involves comparisons like >, >= 2 * nums[j], or a range check on nums[i] - nums[j].
• Phrasing mentions "inversions", "reverse pairs", or "count of smaller after self".

Common templates:

• Classic inversion count: count i < j with nums[i] > nums[j] during the merge step. Example: Global and Local Inversions.
• Reverse pairs: separate two-pointer pass per merge with a stricter 2 * nums[j] threshold. Example: Reverse Pairs.
• Count smaller after self: track original indices through the sort, increment per skip. Example: Count of Smaller Numbers After Self.
• Range sum inversions: merge a prefix-sum array and count pairs whose difference lies in a range. Example: Count of Range Sum.