9.6 Quick Sort

REF.

C.A.R. Hoare. Algorithm 63 (Partition) and Algorithm 65 (find). Communications of the ACM, Volume 4, Number 7, pp. 321-322, 1961.

REF.

C.A.R. Hoare. Quicksort. The Computer Journal, Volume 5, Number 1, pp. 10-15, 1962.

REF.

Robert Sedgewick. Implementing quicksort programs. Communications of the ACM, Volume 21, Number 10, pp. 847-857, 1978.

• Divide and conquer algorithm designed by CAR Hoare in 1962.
• Worst case O(n²) time, but average case O(nlog n) time. Better average case performance than heap sort.