Counting Inversions Adaptively

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)}})$timeintheword-RAMmodelofcomputation,where$Inv$ is the number of inversions.