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.