Quicksort

Divide-Conquer-Combine

Quicksort applies divide-and-conquer paradigm. The three-step process for sorting a typical subarray A[p..r]:

• Divide: Partition the array A[p..r] into two (possibly empty) subarrays A[p..q - 1] and A[q + 1..r] such that each element of A[p..q - 1] is less than or equal to A[q]. A[q] is less than or equal to each element of A[q + 1..r]. It computes the index q.
• Conquer: Sort the two subarrays A[p..q - 1] and A[q + 1..r] recursively.
• Combine: No need to combine because the array is already sorted.

Pseudocode

Overall

Quicksort(A, p, r)
if p < r
    q = PARTITION(A, p, r)
    Quicksort(A, p, q - 1)
    Quicksort(A, q + 1, r)

Partition

Partition(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
    if A[j] <= x
        i = i + 1
        exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1

Reference

• CLRS book