Overview

Quicksort is a highly efficient comparison-based sorting algorithm that uses the divide-and-conquer paradigm. Despite having a worst-case running time of Θ(n²), it is often the practical sorting algorithm of choice because its expected running time is Θ(n lg n) with very small constant factors. It also sorts in place (requiring only O(lg n) additional stack space) and performs well in virtual-memory environments.

The chapter covers the core algorithm and its PARTITION subroutine (Section 7.1), intuitive and formal performance analysis for worst-case, best-case, and average-case scenarios (Sections 7.2 and 7.4), and a randomized variant that eliminates dependence on input ordering (Section 7.3).

Key Concepts

• Divide-and-conquer structure: Quicksort partitions the array around a pivot element, recursively sorts the two resulting subarrays, and requires no combine step since the subarrays are sorted in place.
• Pivot selection: The standard PARTITION procedure uses the last element A[r] as the pivot. The randomized variant selects a uniformly random element, ensuring no particular input triggers worst-case behavior.
• In-place partitioning: The PARTITION procedure (Lomuto's scheme) rearranges elements using only constant extra memory by maintaining two regions — elements ≤ pivot and elements > pivot — separated by index pointers.
• Loop invariant for PARTITION: At the start of each iteration of the for loop, three regions are maintained:

1. A[p..i] contains elements ≤ x (the pivot).

2. A[i+1..j−1] contains elements > x.

3. A[r] = x (the pivot itself).

This invariant is proved via initialization, maintenance, and termination arguments.

• Performance depends on partition balance: Balanced splits yield O(n lg n); maximally unbalanced splits yield Θ(n²). The key insight is that even moderately unbalanced splits (e.g., 9-to-1) still produce O(n lg n) performance.
• Comparison-driven analysis: The total running time is O(n + X), where X is the total number of element comparisons across all PARTITION calls (Lemma 7.1). Analyzing X via indicator random variables yields the expected-case bound.

Algorithms and Techniques

QUICKSORT(A, p, r)

The main recursive procedure:

1. Base case: If p ≥ r, the subarray has zero or one element — do nothing.

2. Partition: Call PARTITION(A, p, r) to get pivot index q, placing A[q] in its final sorted position.

3. Recurse: Recursively sort A[p..q−1] (elements ≤ pivot) and A[q+1..r] (elements > pivot).