Sorting & Searching

Quicksort

An in-place divide-and-conquer sort with O(n log n) expected time and the smallest constants of any comparison sort in practice — but O(n²) worst case if the pivot is chosen badly and the input is adversarial.

Partition around a pivot: smaller elements left, larger right, then recurse on each side
Expected O(n log n); worst case O(n²) on already-sorted input with a naive fixed pivot
In-place: O(log n) stack space from recursion, no auxiliary array
Not stable — partitioning swaps elements past each other regardless of original order
Randomizing the pivot (or using median-of-three) makes the O(n²) worst case cryptographically unlikely rather than adversary-triggerable

Quicksort with Hoare partitioning

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

static int partition(int[] a, int lo, int hi) {
    int pivot = a[lo + ThreadLocalRandom.current().nextInt(hi - lo)];
    int i = lo - 1, j = hi;
    while (true) {
        do { i++; } while (a[i] < pivot);
        do { j--; } while (a[j] > pivot);
        if (i >= j) return j;
        int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
    }
}

Why quicksort usually wins anyway
Factor	Effect
In-place partitioning	no allocation, excellent cache locality
Small constant factor	fewer instructions per comparison than mergesort/heapsort
Tail-call-friendly recursion	recurse into the smaller half first, iterate the larger — bounds stack depth to O(log n)