1. Base case
A single element is already sorted with zero inversions.
if (arr.length <= 1) return [arr, 0]Typorithm · hard
Count Inversions
▷ Interactive algorithm labcount-inversionsdivide-and-conquermergecross-pairscombine-step
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Count Inversions
Divide & Conquer
Augment merge sort: when a right element is placed early, all leftover left elements are inversions.
An inversion is a pair i < j where nums[i] > nums[j].
Counting within each half is recursive; the clever part is counting cross-half inversions during the merge.
Each time a right element jumps ahead of remaining left elements, those left elements are all inversions with it.
Preparing algorithm lab…
01
Inversions split into left, right, cross.
02
Cross pairs are counted at the merge.
03
count += left.length - i.
function countInversions(nums) {
function sortCount(arr) {
if (arr.length <= 1) return [arr, 0];
const mid = Math.floor(arr.length / 2);
const [left, leftCount] = sortCount(arr.slice(0, mid));
const [right, rightCount] = sortCount(arr.slice(mid));
const merged = [];
let i = 0;
let j = 0;
let count = leftCount + rightCount;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
merged.push(left[i]);
i += 1;
} else {
merged.push(right[j]);
j += 1;
count += left.length - i;
}
}
return [merged.concat(left.slice(i), right.slice(j)), count];
}
return sortCount(nums)[1];
}Read the implementation
Connect each part of the code to the concept before you type.
2. Divide
Split the array into two halves to count recursively.
const mid = Math.floor(arr.length / 2)3. Combine counts
Start with inversions counted within each half.
let count = leftCount + rightCount4. Count cross pairs
When a right value is smaller, every remaining left value forms an inversion with it.
count += left.length - i5. Finish merge
Append whatever remains of either half to the merged result.
merged.concat(left.slice(i), right.slice(j))A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.