Counting Inversions Adaptively

Abstract

We give a simple and efficient algorithm for adaptively counting inversions in a sequence of $n$ integers. Our algorithm runs in $O(n+n\sqrt{\lg (Inv/n)})$ time in the word-RAM model of computation, where $Inv$ is the number of inversions.

5 pages