Problem Overview & Intuition

A brute force checks all pairs in O(N²). During Merge Sort, when picking an element from the right subarray because arr[i] > arr[j], every remaining element in the sorted left subarray [i...mid] is also strictly greater than arr[j], contributing mid - i + 1 inversions in O(N log N).

Step-by-Step Approach

1. Divide the array into two halves recursively.
2. Count inversions in left half and right half.
3. During the merge step, whenever arr[i] > arr[j], add mid - i + 1 to inversion count.
4. Return total inversions accumulated.

Optimal Implementation (JavaScript)

function countInversions(arr) {
  const temp = new Array(arr.length);
  function mergeSort(left, right) {
    let inv = 0;
    if (left < right) {
      const mid = Math.floor((left + right) / 2);
      inv += mergeSort(left, mid);
      inv += mergeSort(mid + 1, right);
      inv += merge(left, mid, right);
    }
    return inv;
  }
  function merge(left, mid, right) {
    let i = left, j = mid + 1, k = left, inv = 0;
    while (i <= mid && j <= right) {
      if (arr[i] <= arr[j]) temp[k++] = arr[i++];
      else {
        temp[k++] = arr[j++];
        inv += (mid - i + 1);
      }
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    for (let p = left; p <= right; p++) arr[p] = temp[p];
    return inv;
  }
  return mergeSort(0, arr.length - 1);
}

Complexity Analysis