Pattern visualizer
Count Inversions in Array
The definition invites you to test every pair, which is O(n^2). The way out is to notice that an inversion either lives inside the left half, inside the right half, or straddles the two — so if recursion reports the first two, this level only owes the crossings. And once both halves are sorted, the crossings come cheap: for a right value v, walk a pointer along the left half until the values stop being <= v; everything remaining there is bigger than v AND positioned before it, so the whole tail counts in one go instead of one comparison per pair. Sorting the halves is a side effect, not the goal — it is what makes the block count legal, because pairs inside a half are already tallied and never re-examined. Animated on: A = [5, 3, 2, 4, 1, 6] — count the pairs (i, j) with i < j and A[i] > A[j]. Brute force compares all 15 pairs; merge sort counts them in blocks..
Merge sort counts crossing pairs a block at a time
An inversion is a pair that is out of order: index i before index j, but A[i] > A[j]. Checking every pair means 15 comparisons for just 6 values, and that cost squares as the array grows. Merge sort can count them in blocks instead of one at a time.
1FUNCTION countInversions(A, lo, hi)2 IF lo >= hi3 RETURN 04 mid <- FLOOR((lo + hi) / 2)5 count <- countInversions(A, lo, mid) + countInversions(A, mid + 1, hi)6 i <- lo7 FOR j <- mid + 1 TO hi8 WHILE i <= mid AND A[i] <= A[j]9 i <- i + 110 count <- count + (mid - i + 1)11 MERGE A[lo..mid] AND A[mid + 1..hi] INTO A[lo..hi]12 RETURN count
← / → step · space play · Home restart