Count Inversions — Merge Sort Based

What does it solve?

An inversion is a pair of indices (i, j) with i < j but arr[i] > arr[j] — a measure of how "out of order" an array is. A brute-force check of every pair takes O(N²).

We can count inversions in O(N log N) by piggybacking on merge sort: while merging two sorted halves, every time we take from the right half before exhausting the left half, every remaining left element forms an inversion with it.

The core idea

// merging left[] and right[]:
while i < left.size && j < right.size:
  if left[i] <= right[j]: take left[i++]
  else:
    invCount += (left.size - i)
    take right[j++]

Complexity

Time complexity

O(N log N)

Same recurrence as merge sort: T(N) = 2T(N/2) + O(N) — far better than the O(N²) brute-force pairwise check.

Space complexity

O(N)

Needs a temporary buffer to merge each pair of sorted halves back together.

Examples & edge cases

Live animation

Left half Right half Comparing now Inversion(s) counted Merged & sorted

phase: — depth: — range: —

Merge buffer (sorted result being built for this range)

Step — of —

Left pointer (i)

—

Right pointer (j)

—

+Inversions this step

—

Total inversions

—

running count

Select an example and press Play to start.

✓ Complete

Speed Medium

Step-by-step table

Step	Range	Action	Detail	+Inv	Total

C++ implementation

count_inversions.cpp

#include <bits/stdc++.h>
using namespace std;

long long merge(vector<int>& arr, int low, int mid, int high) {
    vector<int> temp;
    int i = low, j = mid + 1;
    long long invCount = 0;

    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) {
            temp.push_back(arr[i++]);
        } else {
            invCount += (mid - i + 1);   // arr[i..mid] all > arr[j]
            temp.push_back(arr[j++]);
        }
    }
    while (i <= mid)  temp.push_back(arr[i++]);
    while (j <= high) temp.push_back(arr[j++]);

    for (int k = low; k <= high; k++) arr[k] = temp[k - low];
    return invCount;
}

long long countInversions(vector<int>& arr, int low, int high) {
    if (low >= high) return 0;
    int mid = (low + high) / 2;

    long long count = 0;
    count += countInversions(arr, low, mid);       // left half
    count += countInversions(arr, mid + 1, high);  // right half
    count += merge(arr, low, mid, high);          // cross-half inversions
    return count;
}

int main() {
    vector<int> arr = {2, 4, 1, 3, 5};
    cout << "Inversions: " << countInversions(arr, 0, arr.size() - 1) << "\n";
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars