Counting inversions adaptively

• We give a simple and efficient algorithm for counting inversions in an input sequence adaptively.
• Our algorithm improves the existing bounds in the word-RAM model.
• Our algorithm can also be used for adaptive sorting.

Consider a sequence X of n elements, where the number of inversions in X is Inv. We give a simple linear-time transformation that reduces the problem of counting the inversions in X to that of counting inversions within disjoint subsequences of X   of O(1+(Inv/n)2)O(1+(Inv/n)2) elements each. In accordance, we can apply our transformation for counting inversions adaptively in O(nlg⁡(Inv/n))O(nlg⁡(Inv/n))1 time. Alternatively, if the elements are integers, we achieve a running time of O(nlg⁡(Inv/n)) in the Word-RAM model of computation.