Quicksort: Partitioning, Pivots, and Two Textbook Schemes

Understand quicksort: an in-place, divide-and-conquer sort that picks a pivot, partitions the array around it, and recursively sorts the two resulting pieces — average-case O(n log n) with small constants, at the cost of an O(n²) worst case if the pivot is chosen badly.

• The default general-purpose sort when average-case speed and low memory overhead (in-place, no auxiliary array) matter more than a worst-case guarantee.
• A canonical example of divide-and-conquer: understanding quicksort's recursion makes mergesort, binary search, and most tree algorithms easier to reason about.
• A standard whiteboard/interview exercise — expect to be asked to implement partitioning, explain the worst case, or trace it by hand.

The algorithm: partition, then recurse

Both books express the same three steps. Pick a pivot from the subarray, partition so everything ≤ pivot ends up to its left and everything ≥ pivot ends up to its right, then recursively sort each side:

java
void quicksort(int[] a, int lo, int hi) {
    if (hi <= lo) return;
    int pivotIndex = partition(a, lo, hi);
    quicksort(a, lo, pivotIndex - 1);
    quicksort(a, pivotIndex + 1, hi);
}

The two books differ entirely in how partition works — and that difference is worth knowing, since it's a common source of off-by-one bugs when implementing quicksort from memory.

Cormen's Lomuto partition: one forward scan, pivot at the end

CLRS picks the last element as the pivot and walks the subarray once with two indices, i tracking the boundary of the "≤ pivot" region:

java
int partition(int[] a, int lo, int hi) {
    int pivot = a[hi];       // CLRS picks the last element
    int i = lo - 1;          // boundary of the "≤ pivot" region
    for (int j = lo; j < hi; j++) {
        if (a[j] <= pivot) {
            i++;
            swap(a, i, j);
        }
    }
    swap(a, i + 1, hi);      // pivot lands just right of the "≤" region
    return i + 1;
}

Sedgewick's Hoare-style partition: two pointers scanning inward

Algorithms, 4th Ed. instead picks the first element as the pivot and scans from both ends toward the middle, swapping out-of-place pairs as it goes:

java
int partition(int[] a, int lo, int hi) {
    int pivot = a[lo];               // Sedgewick picks the first element
    int i = lo, j = hi + 1;
    while (true) {
        while (a[++i] < pivot) if (i == hi) break;
        while (a[--j] > pivot) if (j == lo) break;
        if (i >= j) break;
        swap(a, i, j);
    }
    swap(a, lo, j);                  // pivot lands at the meeting point
    return j;
}

Both are correct, in-place, and O(n) per partition call — the difference is scan direction and which end holds the pivot, not asymptotic behavior.

Watch it happen: the actual partitioning and swaps

Sedgewick's own running example shuffles the letters of "QUICKSORT" and sorts them. This runs the real Hoare-style partitioning shown above, step by step — every pivot pick and every exchange, not just where each letter ends up:

Average case vs. worst case

A pivot that splits the subarray roughly in half each time gives the same recurrence as mergesort, T(n) = 2T(n/2) + O(n), which solves to O(n log n). A pivot that's always the smallest or largest element (already-sorted input with a naive first/last-element pivot choice) degrades every partition to a size-1/size-(n−1) split, giving T(n) = T(n-1) + O(n), which solves to O(n²) — the worst case both books derive in detail.

• Worst-case O(n²) on adversarial or already-sorted input, unlike mergesort's guaranteed O(n log n) — the standard mitigation both books cover is randomizing the pivot choice (shuffle the array first, or pick a random element as pivot) so the worst case becomes vanishingly unlikely rather than triggered by common inputs like sorted or reverse-sorted data.

• Not stable — equal elements can be reordered relative to each other during partitioning, unlike mergesort or insertion sort. If preserving the original relative order of equal keys matters (e.g. sorting already-date-sorted transactions by amount), a stable sort is the safer default.

• In production Java, you're not calling either textbook implementation — Arrays.sort() on a primitive array (int[], long[], etc.) uses a dual-pivot quicksort, not the single-pivot scheme either book teaches, and Arrays.sort() on an Object[]/generic array uses TimSort (a stable merge/insertion-sort hybrid), not quicksort at all — because stability matters for objects with custom compareTo()/Comparator logic but not for raw primitives:

  java
  int[] nums = {5, 3, 1, 4, 2};
  Arrays.sort(nums);                 // dual-pivot quicksort, unstable, fine for primitives
  
  Integer[] boxed = {5, 3, 1, 4, 2};
  Arrays.sort(boxed);                // TimSort, stable, used because equal-key order can matter for objects