Senior LevelData Structures & Algorithms
How do you count Inversions in an array using modified Merge Sort?
ā Interview Prompt: Count the number of inversions (i < j but arr[i] > arr[j]) in O(N log N) using modified Merge Sort.
Inversion Count: Number of pairs $(i, j)$ where $i < j$ and $\text{arr}[i] > \text{arr}[j]$. Measures how far an array is from being sorted.
Modified Merge Sort: $O(N \log N)$
During the merge step, when an element from the right half is placed before an element from the left half, all remaining left-half elements at that position form inversions.
Count = leftHalf.length - leftPointer for each right element picked.
Code Implementation Example
typescript
function countInversions(arr: number[]): number {
function mergeCount(arr: number[]): [number[], number] {
if (arr.length <= 1) return [arr, 0];
const mid = arr.length >> 1;
const [left, lc] = mergeCount(arr.slice(0, mid));
const [right, rc] = mergeCount(arr.slice(mid));
let count = lc + rc, i = 0, j = 0;
const merged: number[] = [];
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
merged.push(left[i++]);
} else {
count += left.length - i; // all remaining left elements are inversions!
merged.push(right[j++]);
}
}
return [[...merged, ...left.slice(i), ...right.slice(j)], count];
}
return mergeCount(arr)[1];
}
console.log(countInversions([8, 4, 2, 1])); // 6š”Counting inversions with modified Merge Sort ā O(N log N).
šÆ Interview Key Takeaway
Modified Merge Sort counts inversions in O(N log N). Inversion count measures sorting distance and is used in recommendation similarity metrics and bioinformatics.
#DSA#Inversions#Merge Sort#Divide and Conquer#Senior
Back to all Data Structures & Algorithms Questionsā