Quicksort
Quicksort, like merge sort, applies the divid-and-conquer paradigm. Here is the three-step divide-and-conquer process for sorting a typical subarray A[p..r]: Divide: Partition (rearrange) the array A[p..r] into two (possibly empty) subarrays A[p..q-1] and A[p+1..r] such that each element of A[p..q-1] is less than or equal to A[q], which is, in turn, less than or equal to each element of A[p+1..r]. Compute the index q as part of this partitioning procedure. Conquer: Sort the two subarrays A[p..q-1] and A[q+1..r] by recursive calls to quicksort. Combine: Because the subarrays are already sorted, no work is needed to combine them: the entire array A[p..r] is now sorted. The following procedure implements quicksort: QUICKSORT(A, p, r) if p < r q = PARTITION(A, p, r) QUICKSORT(A, p, q - 1) QUICKSORT(A, q + 1, r) To sort an entire array A, the initial call is QUICKSORT(A, 1, A.length). Partitioning the array The key to the algorithm is the PARTITION procedure,