DSA Tracker

Visualize

Count Inversions

Merge sort counts crossing pairs a block at a time

time O(n log n)space O(n)

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.

Details

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.

Problem:Count InversionsMedium

Merge sort counts crossing pairs a block at a time

step 1 / 10

5
[0]
3
[1]
2
[2]
4
[3]
1
[4]
6
[5]

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.

Pseudocode
1FUNCTION countInversions(A, lo, hi)
2  IF lo >= hi
3    RETURN 0
4  mid <- FLOOR((lo + hi) / 2)
5  count <- countInversions(A, lo, mid) + countInversions(A, mid + 1, hi)
6  i <- lo
7  FOR j <- mid + 1 TO hi
8    WHILE i <= mid AND A[i] <= A[j]
9      i <- i + 1
10    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

Every step in words

Show all 10 steps
  1. 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.
  2. Split at mid=2: [5, 3, 2] and [4, 1, 6]. Any inversion is either wholly inside the left half, wholly inside the right half, or straddles the two — there is no fourth case. So recursion handles the first two, and this frame only has to count the crossings.
  3. Sub-range 0..1 is finished. The original chunk [5, 3] held 1 inversion, of which 1 crosses the split at 0: 5 sits before 3 and exceeds it. It is now sorted to [3, 5], which is safe: those pairs are already counted, and every level above only ever compares this chunk against values outside it. Running total 1.
  4. Sub-range 0..2 is finished. The original chunk [5, 3, 2] held 3 inversions, of which 2 cross the split at 1: [3, 5] both sit before 2 and exceed it. It is now sorted to [2, 3, 5], which is safe: those pairs are already counted, and every level above only ever compares this chunk against values outside it. Running total 3.
  5. Sub-range 3..4 is finished. The original chunk [4, 1] held 1 inversion, of which 1 crosses the split at 3: 4 sits before 1 and exceeds it. It is now sorted to [1, 4], which is safe: those pairs are already counted, and every level above only ever compares this chunk against values outside it. Running total 4.
  6. Sub-range 3..5 is finished. The original chunk [4, 1, 6] held 1 inversion, and it does not cross the split at 4 — every value in [1, 4] is already <= every value in [6], so this merge adds nothing. It is now sorted to [1, 4, 6], which is safe: those pairs are already counted, and every level above only ever compares this chunk against values outside it. Running total 4.
  7. Right-half value A[3]=1: from index 0 onward [2, 3, 5] all sit before 1 and exceed it, so that is 3 inversions found by ONE comparison instead of 3. Running total 7.
  8. Right-half value A[4]=4: [2, 3] are <= 4, so those pairs are already in order and i steps past them for good — i never rewinds, which is what keeps this whole sweep linear, and from index 2 onward 5 sits before 4 and exceeds it, so that is 1 inversion. Running total 8.
  9. Right-half value A[5]=6: [5] is <= 6, so that pair is already in order and i steps past it for good, and i has run off the end of the left half, so nothing there is bigger than 6 — it contributes none. Running total 8.
  10. The last merge produces [1, 2, 3, 4, 5, 6], but the sorting was only ever the vehicle — the answer is the 8 crossings that were tallied on the way down. Brute force needs all 15 pairs to say the same thing; this says it in O(n log n).

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Count Inversions in the editorAll Sorting problemsBack to roadmap