On the Complexity of Inversions
Abraham Waksman · IEEE Transactions on Computers · 1970
The inversion process which entails the interchange of two adjacent elements in a list is fundamental to most practical sorting algorithms.Consequently, one can utilize the inversions associated with a given permutation as its measure of complexity. To this end a recurrence relation is established.