Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 7

The authors then provide an algorithm for quicksort along with an algorithm of partition and prove that partition takes time. The authors then prove that worst-case time for quicksort is and the best-case time for quicksort is . The worst case happens when the array is already sorted.

The authors then provide a randomized algorithm for partition where pivot is randomly chosen. The authors prove that the worst-case running time of quick-sort is using substitution method. The authors also prove that expected running time of the randomized quicksort algorithm is .