Merge-Based Problems: Union, Intersection and Inversions

The merge step is worth more than merge sort. Once two arrays are sorted, a single pass with two pointers answers a whole family of questions, and the only thing that changes between them is what you do at each comparison.

Union and intersection

Both are the same loop. Compare the two front values, then:

Both are O(n + m) once the inputs are sorted, and use no extra memory beyond the output. The hash-set alternative is also O(n + m) on average but loses the ordering and costs memory; on already-sorted input the two-pointer version is strictly better.

The detail to get right is duplicates. If the inputs can contain repeats and the output should not, compare each candidate against the last thing you emitted before emitting it.

Counting inversions

An inversion is a pair of positions i < j where a[i] > a[j]: a pair that is out of order. The count measures how far from sorted an array is. Zero means sorted; n(n-1)/2 means exactly reversed.

It has real uses: it is the number of swaps bubble sort would perform, and as Kendall's tau distance it measures how much two rankings disagree, which is how you compare a recommender's output against a user's actual preference order.

The obvious algorithm checks all pairs in O(n²). The trick is that merge sort already compares elements from different halves, and it does so in batches.

During a merge, when you take a value from the right half, every element still remaining in the left half is greater than it, and each of those is sitting at an earlier index. So they are all inversions with it, and you can add the whole batch at once with count += left.length - i instead of counting them one at a time.

That single line is what collapses O(n²) into O(n log n). Everything else is just merge sort.

Inversions between the two halves are counted during their merge; inversions within a half are counted by the recursive calls. So every pair is counted exactly once, at the level where the two elements first end up in different halves.

In code

function countInversions(a) {
  let count = 0;

  function sortAndCount(arr) {
    if (arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = sortAndCount(arr.slice(0, mid));    // inversions inside the left
    const right = sortAndCount(arr.slice(mid));      // inversions inside the right

    const out = [];
    let i = 0, j = 0;
    while (i < left.length && j < right.length) {
      if (left[i] <= right[j]) {
        out.push(left[i++]);
      } else {
        // Every remaining left element is greater than right[j], and each
        // sits at an earlier index. Count the whole batch in one go.
        count += left.length - i;
        out.push(right[j++]);
      }
    }
    while (i < left.length) out.push(left[i++]);
    while (j < right.length) out.push(right[j++]);
    return out;
  }

  sortAndCount(a);
  return count;
}

// countInversions([1, 2, 3]) -> 0
// countInversions([3, 2, 1]) -> 3

Check yourself