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 elements each. In accordance, we can apply our transformation for counting inversions adaptively in time. Alternatively, if the elements are integers, we achieve a running time of in the Word‐RAM model of computation.
