Inversion Counting

Return the number of inversions in a vector. That is, the number of pairs of indices \({i, j}\) such that \(i < j\) and \(A_i > A_j\).

Complexity: \(\mathcal{O}(N\log(N))\)

Code

Inversion Counting

// Inversion Counting {{{
int inversions(vector<int> const& A) {
  ordered_set<pair<int, int>> OS;
  int ans = 0;
  for (int i = 0; i < size(A); i++) {
    ans += OS.size() - OS.order_of_key({A[i], i});
    OS.insert({A[i], i});
  }
  return ans;
}
//}}}