Quicksort, like merge sort, is based on the divide-and-conquer. Here is the three-step divide-and-conquer process for sorting a typical subarray A[pr].
  • Divide:Partition (rearrange) the array A[pr] into two (possibly empty) subarrays A[pq - 1] and A[q 1 ‥r] such that each element of A[pq - 1] is less than or equal to A[q], which is, in turn, less than or equal to each element of A[q 1 ‥r]. Compute the index q as part of this partitioning procedure.