Count Inversions (Based on Merge Sort Concept)

Inversion is (i, j) pair which is not in the correct order i.e. for i < j, A[i] > A[j].

A = [10, 5 , 3, 2 , 1, 6, 3, 7, 8] Inversions : (0, 1) (1, 2) (0, 2) (1, 6) (0, 3) ans so many inversions. (0, 4) (0, 5) (0, 6) (0, 7)

  • This can be easily solved in O(n^2).
  • But we need to solve in O(n log n).

All Inversions:

Dry Run:

Built with LogoFlowershow