Count Inversions

The problem. Given an array nums, count its inversions: pairs of indexes i < j with nums[i] > nums[j]. The count measures how far the array is from sorted — 0 for a sorted array, n(n − 1)/2 for a reversed one.

Example

nums = [2, 4, 1, 3, 5]  ->  3   (2>1, 4>1, 4>3)
nums = [5, 4, 3, 2, 1]  ->  10
nums = [1, 2, 3, 4]     ->  0

The idea: count while merging

Split the array in half. Every inversion is either inside the left half, inside the right half, or across (left value bigger than a right value). The first two are counted recursively. For the third, sort both halves — merge sort does that anyway — and look at the merge: when the merge takes a[j] from the right half because it's smaller than a[i], it's also smaller than every value still waiting in the left half (they're sorted, all at least a[i]). That's mid − i inversions counted in one step, instead of one at a time.

1. Brute force: check every pair

1function countInversions(nums) {2  let count = 0;3  for (let i = 0; i < nums.length; i++) {4    for (let j = i + 1; j < nums.length; j++) {5      if (nums[i] > nums[j]) count++;6    }7  }8  return count;9}

Time O(n²), space O(1).

2. Merge sort that counts

1function countInversions(nums) {2  const a = [...nums];3  const sortCount = (lo, hi) => {                 // sorts a[lo..hi), returns the inversions inside it4    if (hi - lo <= 1) return 0;5    const mid = (lo + hi) >> 1;6    let count = sortCount(lo, mid) + sortCount(mid, hi);7    const merged = [];8    let i = lo, j = mid;9    while (i < mid && j < hi) {10      if (a[i] <= a[j]) merged.push(a[i++]);11      else {12        count += mid - i;                         // a[j] is smaller than everything left in the left half13        merged.push(a[j++]);14      }15    }16    while (i < mid) merged.push(a[i++]);17    while (j < hi) merged.push(a[j++]);18    for (let k = 0; k < merged.length; k++) a[lo + k] = merged[k];19    return count;20  };21  return sortCount(0, a.length);22}

Time O(n log n), space O(n). It's merge sort with one extra addition, so it costs the same. Use a 64-bit counter: n = 10⁵ can have about 5 × 10⁹ inversions. And <= matters — equal values are not an inversion, so a tie takes from the left without counting.

Comparing the approaches

Inversions also measure work: insertion sort and bubble sort make exactly one swap or shift per inversion.

Edge cases to test

Variations