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 $ \Theta (n) $ time. The authors then prove that worst-case time for quicksort is $ \Theta (n^2) $ and the best-case time for quicksort is $ \Theta (n \lg n) $. 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 $ \Theta (n^2) $ using substitution method. The authors also prove that expected running time of the randomized quicksort algorithm is $ O (n \lg n) $.