2 replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/ edited Apr 13 '17 at 12:48 Inversions are one way to measure "disorder" in a list: Let $$A[1..n]$$ be an array of $$n$$ distinct numbers. If $$i < j$$ and $$A[i] < A[j]$$ then the pair $$(i,j)$$ is an inversion of $$A$$. However, it's not the only such measure. In general, this concept is formalized in the notion of presortedness - roughly: An integer function on a permutation $$\sigma$$ of a totally ordered set that reflects how much $$\sigma$$ differs from the total order. The survey papers by Mannila  and Estivill-Castro & Wood  might be good places to start. The question How to measure "sortedness"How to measure "sortedness" is related. Inversions are one way to measure "disorder" in a list: Let $$A[1..n]$$ be an array of $$n$$ distinct numbers. If $$i < j$$ and $$A[i] < A[j]$$ then the pair $$(i,j)$$ is an inversion of $$A$$. However, it's not the only such measure. In general, this concept is formalized in the notion of presortedness - roughly: An integer function on a permutation $$\sigma$$ of a totally ordered set that reflects how much $$\sigma$$ differs from the total order. The survey papers by Mannila  and Estivill-Castro & Wood  might be good places to start. The question How to measure "sortedness" is related. Inversions are one way to measure "disorder" in a list: Let $$A[1..n]$$ be an array of $$n$$ distinct numbers. If $$i < j$$ and $$A[i] < A[j]$$ then the pair $$(i,j)$$ is an inversion of $$A$$. However, it's not the only such measure. In general, this concept is formalized in the notion of presortedness - roughly: An integer function on a permutation $$\sigma$$ of a totally ordered set that reflects how much $$\sigma$$ differs from the total order. The survey papers by Mannila  and Estivill-Castro & Wood  might be good places to start. The question How to measure "sortedness" is related. 1 answered Nov 20 '14 at 21:05 rphv 1,38799 silver badges2323 bronze badges Inversions are one way to measure "disorder" in a list: Let $$A[1..n]$$ be an array of $$n$$ distinct numbers. If $$i < j$$ and $$A[i] < A[j]$$ then the pair $$(i,j)$$ is an inversion of $$A$$. However, it's not the only such measure. In general, this concept is formalized in the notion of presortedness - roughly: An integer function on a permutation $$\sigma$$ of a totally ordered set that reflects how much $$\sigma$$ differs from the total order. The survey papers by Mannila  and Estivill-Castro & Wood  might be good places to start. The question How to measure "sortedness" is related.