👩💻 Join our community of thousands of amazing developers!

Original article Counting inversions via rank queries | blog :: Brent -> String Count the number of inversions of a sequence in \(O(n \lg n)\) inversion Given a sequence \(a_1, a_2, \dots, a_n\) , an inversion is a pair of positions \(i, j\) such that \(a_i\) and \(a_j\) are in the “wrong order”, that is, \(i < j\) but \(a_i > a_j\) . There can be up to \(n(n-1)/2\) inversions in the worst case, so we cannot hope to count them in faster than quadratic time by simply incrementing a counter....