Quicksort: partition drama and pivot choice

One pivot reorganizes the whole subarray

Quicksort picks a pivot element, partitions the subarray so that everything smaller lies to its left and everything larger to its right, then recurses on each side. With a good pivot, the recursion tree has depth about log n and total work is Θ(n log n). With a terrible pivot on adversarial input, the depth becomes n and performance collapses to Θ(n²). Pivot choice is the whole story.

public static void quickSort(int[] a) {
    quickSort(a, 0, a.length - 1);
}

private static void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

private static int partition(int[] a, int lo, int hi) {
    int pivot = a[hi];          // simple choice; see notes for better ones
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (a[j] <= pivot) {
            i++;
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    }
    int t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;
    return i + 1;
}

Why choice of pivot matters so much

• Last element as pivot: O(n²) on already-sorted input — a real bug in old implementations.
• Random pivot: expected O(n log n), cannot be defeated by a pre-chosen adversarial input.
• Median-of-three (first, middle, last): cheap heuristic that dodges common bad cases.
• Dual-pivot (Java): splits into three regions and reduces comparisons on realistic data.