How do you measure how “shuffled” an array is? Not just “is it sorted or not” — but how far from sorted?

One natural measure: count the number of inversions. An inversion is a pair (i, j) where i < j but arr[i] > arr[j] — two elements that are in the wrong relative order.

Each arc connects a pair that's out of order. Tap any cell to see which inversions it participates in. A fully sorted array has zero arcs. A reverse-sorted array would be a tangled mess of n*(n-1)/2 arcs — every pair is wrong.

The brute force approach is simple: check every pair. But how many pairs are there? For a 5-element array, look at the grid of all comparisons:

Every cell is a pair you'd need to check — tap one to see the comparison. That's O(n^2) work. Fine for small arrays, but for large ones, you'd like something faster. Here's the challenge: you have a limited comparison budget. Can you count all the inversions before it runs out?

You've got a limited comparison budget and a shuffled array. Each comparison checks one pair of elements and determines whether they form an inversion (out of order) or not. The brute force approach burns through O(n^2) comparisons — one for every pair. But your budget is tighter than that. Can you count all the inversions before you run out of comparisons? If you can't, that's evidence that brute force is wasteful — and motivation to find a smarter approach.

Counting inversions by brute force is O(n^2). You need to compare every pair. We've been here before — a problem that seems to require quadratic work.

But think about what's happening when you merge sort an array. During the merge step, you have two sorted halves and you're combining them. When you pick an element from the right half before all elements in the left half have been consumed, that right-side element is smaller than every remaining left-side element. Those remaining left-side elements form inversions with it.

That's the key: when the merge picks from the right, it doesn't just find one inversion — it finds all of them at once. Every remaining element in the left half is an inversion with the element being placed from the right.

In other words: every time the merge step picks from the right half, it reveals exactly how many inversions that element participates in — it's the number of elements still remaining in the left half.

Merge sort is already doing the comparisons you need. The inversion count is hiding inside the merge step, waiting to be tallied. Let's watch the merge step in action and see the inversions appear.

Watch a merge step in slow motion. Two sorted halves are being combined into one sorted sequence. Every time the merge picks an element from the right half, it means that element is smaller than everything remaining in the left half — and each of those remaining left-half elements forms an inversion with it. One pick from the right reveals multiple inversions simultaneously. Count them as they appear and see how the merge does the counting work for free.

Every time the merge picks from the right half, the number of inversions discovered equals the number of elements remaining in the left half. That's not a coincidence — it's a direct consequence of how sorted sub-sequences interleave.

Think about why this works. After the recursive calls, both halves are sorted internally. When you're merging and the next element comes from the right half, it means that element is smaller than everything remaining in the left half. And since the left half is sorted, “everything remaining” forms a contiguous block. If there are 4 elements left in the left half, that single right-half pick reveals exactly 4 inversions in one shot. No need to check each pair individually.

The recursion cleanly partitions the work. Inversions come in three flavors: (1) both elements in the left half, (2) both elements in the right half, (3) one from each. The recursive calls handle flavors 1 and 2. The merge step handles flavor 3 — and only flavor 3. There's no double-counting, no missed pairs.

See it concretely: the left half has [2, 5, 7, 9] and we're about to pick 3 from the right. How many inversions does that single pick reveal?

Picture the recurrence as a tree. At the top level, the merge step scans n elements and counts the cross-boundary inversions. At the next level down, two merges of n/2 elements each count their own cross-boundary inversions. At the bottom, pairs of single elements have no internal inversions. The total work at each level is O(n) — exactly like merge sort — giving: total inversions = inversions in left half + inversions in right half + inversions discovered during merge. The recurrence is T(n) = 2T(n/2) + O(n), which resolves to O(n log n).

Can you construct the expression that captures how many inversions a single merge-from-right event reveals?

You've seen the merge reveal inversions in real time. Now formalize it. When the merge picks element x from the right half and there are k elements remaining in the left half, how many inversions does that single pick reveal? Build the expression that captures this count. Getting this formula right is the entire difference between “sort an array” and “count inversions” — it's the one line of bookkeeping that transforms merge sort into an inversion counter.

The beautiful thing about this algorithm is how little code it requires beyond standard merge sort. You take the merge sort implementation you already know, and add a single counter increment at the right moment — when you pick from the right half during the merge.

That's it. The same O(n log n) merge sort, with one line of bookkeeping, gives you the inversion count for free.

This is a powerful D&C design pattern: piggyback on existing structure. Instead of solving the inversion-counting problem from scratch, you recognize that merge sort already compares the elements you care about, in exactly the order you need. You just need to count what it's already discovering.

Let's connect each moment in the merge process to the line of code that implements it.

Now connect the merge visualization to the actual implementation. You'll see a merge sort in code, and at each step in the merge, you need to identify the moment where an inversion is counted. The code is nearly identical to standard merge sort — the only addition is a counter that increments at exactly the right moment. Map each merge event to the corresponding line of code. This is the “piggyback” pattern: instrumenting an existing algorithm to extract additional information at no extra cost.

function countInversions(arr: number[]): number {

  if (arr.length <= 1) return 0;

  const mid = Math.floor(arr.length / 2);

  const left = arr.slice(0, mid);

  const right = arr.slice(mid);

  let count = countInversions(left) + countInversions(right);

  // Merge and count cross-inversions

  let i = 0, j = 0;

  const merged: number[] = [];

  while (i < left.length && j < right.length) {

    if (left[i] <= right[j]) {

      merged.push(left[i++]);

    } else {

      // ALL remaining left elements are inversions!

      count += mid - i;

      merged.push(right[j++]);

    }

  }

  // ... append remaining elements

  return count;

}

You turned an O(n^2) counting problem into an O(n log n) algorithm by recognizing that merge sort was already doing the hard work. One counter increment in the merge step — that's the entire difference between “sort an array” and “count inversions.”

The deeper principle: when you need information about pair relationships in an array, ask yourself — does any existing D&C algorithm already compare these pairs as a side effect? If so, you might be able to extract your answer by instrumenting that algorithm rather than building a new one from scratch.

This is the second time we've seen merge sort as a foundation. First as a sorting algorithm, now as an inversion counter. Next, we'll zoom out and compare the two major families of recursive algorithms — and learn to tell them apart on sight.