Which measure of sortedness explains the phase transition in Quicksort's runtime?
Inversions are one way to measure "disorder" in a list:


  Let $A[1..n]$ be an array of $n$ distinct numbers.  If $i &lt; j$ and $A[i] &lt; 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 [1] and Estivill-Castro &amp; Wood [2] might be good places to start. 

The question How to measure "sortedness" is related.



[1] Heikki Mannila. "Measures of Presortedness and Optimal Sorting Algorithms." IEEE Transactions on Computers 34.4 (1985): 318-325.

[2] Estivill-Castro, Vladmir, and Derick Wood. "A survey of adaptive sorting algorithms." ACM Computing Surveys (CSUR) 24.4 (1992): 441-476.