← Create New Paste

Counting Inversions with Merge Sort: An Interview Classic

3 views
An inversion in an array is a pair of indices (i, j) with i < j but a[i] > a[j]. Counting them measures how far an array is from sorted: a sorted array has zero inversions, and a reverse-sorted array of n elements has n(n-1)/2. Interviewers like this problem because the O(n^2) answer is obvious, while the O(n log n) answer requires modifying an algorithm you already know. Brute force Check every pair: def count_inversions_slow(a): n = len(a) return sum(1 for i in range(n) for j in range(i + 1, n) if a[i] > a[j]) It's correct, but at 10^5 elements it means billions of comparisons. Say it first, then move on. The key idea: inversions split across halves Split the array into a left half and a right half. Every inversion is one of three kinds: 1. Both elements in the left half. 2. Both elements in the right half. 3. One element in each half (the left element is larger). The first two are counted recursively. The third kind is the clever part: if both halves are already sorted, you can count cross inversions while merging. When you take an element from the right half because it is smaller than the current left element, it is smaller than every remaining element in the left half too. So you add the number of remaining left elements to the count. def count_inversions(a): def sort_count(arr): if len(arr) <= 1: return arr, 0 mid = len(arr) // 2 left, x = sort_count(arr[:mid]) right, y = sort_count(arr[mid:]) merged, i, j, cross = [], 0, 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: merged.append(left[i]) i += 1 else: merged.append(right[j]) cross += len(left) - i j += 1 merged.extend(left[i:]) merged.extend(right[j:]) return merged, x + y + cross return sort_count(list(a))[1] Note the <= in the comparison. Equal elements are not inversions, so we take from the left first when values tie. This is a detail interviewers often probe. Complexity The merge step stays linear, so the recurrence is T(n) = 2T(n/2) + O(n), which gives O(n log n) time and O(n) extra space. Walkthrough For [3, 1, 2]: the left half is [3] and the right half is [1, 2]. When merging, 1 < 3 adds 1 (one left element remains), and 2 < 3 adds another 1. That's 2 inversions in total: (3,1) and (3,2). Alternative: Fenwick tree You can also scan from the right and use a Binary Indexed Tree over compressed values to count how many smaller elements you've already seen. That's also O(n log n), and it's worth mentioning if the interviewer asks for an online or streaming variant. Where it shows up - Similarity of rankings: Kendall tau distance between two orderings is an inversion count. - "Count of smaller numbers after self", "reverse pairs" (a[i] > 2*a[j]) and "global vs local inversions" are all close cousins. - Minimum adjacent swaps to sort an array equals the number of inversions. Presenting it well State the three-way split clearly before coding; that's the insight being tested. Then emphasize that sorting the halves is what makes the cross count cheap. If you lose track of your explanation when the clock is running, Linkjob AI (https://linkjob.ai) gives real-time help during job interviews and technical interviews, helping you keep your reasoning clear from brute force to the optimal solution.
Created Nov 16, 2026 17:03 Expires Nov 16, 2027 17:03