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 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, which rearranges the subarray A[p..r] in place. PARTITION(A, p, r) x = A[r] i = p - 1 f...