Inversion count


Learn more...

Lets define inversion as pair of indicies `i, j` such that `i < j` and `a_i >= a_j` (a is our array)

And inversion count of an array is the number of such pairs

Algorithm here has a complexity `O(nlog_2n)` and uses the idea of merge sort

There are some other algorithms, approaches (BIT, Search trees), but the trick with the merge sort i think is way more elegant