7.1 Description of Quicksort

Quicksort is an in-place divide-and-conquer sorting algorithm. Its efficiency comes from partitioning the array around a chosen pivot so that smaller elements move to the left and larger ones to the right. The algorithm then recursively sorts the two sides.

• Divide: Use PARTITION(A, p, r) to rearrange the subarray so that:
  • A[p : q−1] ≤ pivot = A[q]
  • A[q+1 : r] > pivot The pivot ends in its correct final position.
• Conquer: Recursively call:
  • QUICKSORT(A, p, q−1)
  • QUICKSORT(A, q+1, r)
• Combine: Nothing to do. both halves are already sorted.

QUICKSORT(A, p, r)
  if p < r
    // Partition the subarray around the pivot, which ends up in A[q].
    q = PARTITION(A, p, r)
    QUICKSORT(A, p, q-1) // recursively sort the low side
    QUICKSORT(A, q+1, r) // recursivey sort the high side

In the PARTITION:

• Choose pivot as A[r].
• Maintain an index i for the boundary of elements ≤ pivot.
• Scan with j; whenever A[j] ≤ pivot, increment i and swap.
• After the scan, place pivot at i+1.
• Return i+1 as the pivot’s final index.

This ensures correct separation of elements and enables recursive sorting.

PARTITION(A, p, r)
  x = A[r]                      // the pivot
  i = p – 1                     // highest index into the low side
  for j = p to r – 1            // process each element other than the pivot
    if A[j] ≤ x                 // does this element belong on the low side?
      i = i + 1                   // index of a new slot in the low side
      exchange A[i] with A[j]     // put this element there
  exchange A[i + 1] with A[r]   // pivot goes just to the right of the low side
  return i + 1                  // new index of the pivot

7.2 Performance of Quicksort

• Quicksort is often the practical choice for sorting despite a worst-case time of $Θ(n²)$.
• Its expected running time for distinct elements is $Θ(n log n)$, with small constants.
• It sorts in-place (no extra array needed) and works well in virtual memory environments.