Count Inversions

Tags

Count Inversions

Category

Sorting

Difficulty

Hard

Problem Statement

Given an array of integers, count the number of inversions. An inversion is a pair of indices (i, j) such that i < j and array[i] > array[j]. In other words, count how many pairs are out of their natural sorted order.

Intuition

A brute-force approach checks all pairs in O(n^2). However, Merge Sort naturally encounters inversions during the merge step: when an element from the right half is chosen before remaining elements in the left half, each of those remaining left elements forms an inversion with it. By counting these during merge, we piggyback on Merge Sort's O(n log n) structure.

Approach

  1. Implement a modified Merge Sort that returns both the sorted array and the inversion count.
  2. Recursively sort and count inversions in the left half and right half.
  3. During the merge step, whenever an element from the right half is placed before remaining elements of the left half, add the number of remaining left elements to the inversion count (those are all "split inversions").
  4. The total inversions = left inversions + right inversions + split inversions.

Pseudocode

function countInversions(array):
    if length(array) <= 1:
        return array, 0

    mid = length(array) / 2
    left, leftInv = countInversions(array[0..mid])
    right, rightInv = countInversions(array[mid..end])
    merged, splitInv = mergeAndCount(left, right)

    return merged, leftInv + rightInv + splitInv

function mergeAndCount(left, right):
    result = []
    inversions = 0
    i = 0
    j = 0

    while i < length(left) and j < length(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            inversions += length(left) - i
            j += 1

    // append remaining elements from left and right
    result.extend(left[i..])
    result.extend(right[j..])

    return result, inversions

Time & Space Complexity

  • Time: O(n log n) — same as Merge Sort; the counting is done within the merge step at no additional asymptotic cost.
  • Space: O(n) — for the auxiliary arrays used during merging, plus O(log n) recursion stack.

Key Insights

  • When right[j] < left[i], all elements left[i..end] form inversions with right[j] because the left half is already sorted internally.
  • The inversion count measures how far an array is from being sorted. A sorted array has 0 inversions; a reverse-sorted array has n*(n-1)/2 inversions (the maximum).
  • This is a classic example of augmenting a divide-and-conquer algorithm with additional bookkeeping.
  • Using <= (not <) in the merge comparison ensures we do not count equal elements as inversions.

Edge Cases

  • Sorted array: 0 inversions.
  • Reverse-sorted array: n*(n-1)/2 inversions.
  • Array with all identical elements: 0 inversions.
  • Array of length 0 or 1: 0 inversions.
  • Array with exactly one inversion: returns 1.

Linked mentions