Quicksort: Partition and Conquer

"Merge sort divides blindly down the middle. Quicksort divides cleverly around a pivot — and that cleverness makes it usually faster, but occasionally catastrophic. The whole story is in how you pick the pivot."

The Algorithm

Quicksort is the other great divide-and-conquer sort, but it does its work before the recursion instead of after. Pick a pivot element. Partition the array so everything smaller than the pivot goes left and everything larger goes right — now the pivot is in its final sorted position. Then recursively quicksort the left part and the right part. There's no merge step: once both sides are sorted, the whole thing already is. The clever work is the partition; the combine is free.

Why It's Usually the Fastest

Quicksort's killer feature is that it partitions in place — just swapping elements within the array, no O(n) temporary buffer like merge sort needs. That means less memory and, crucially, excellent cache locality (it works on a contiguous array, the cache advantage from the arrays lesson). In practice, on big random arrays, quicksort typically beats merge sort despite the same O(n log n) average, purely on those constant factors. It's the default in many language libraries' unstable-sort path for exactly this reason.

The Catch: Bad Pivots Cause O(n²)

Here's quicksort's dark side. If the pivot is consistently terrible — say you always pick the first element, and the array is already sorted — then each partition peels off just one element instead of splitting in half. That's n levels of recursion, each doing O(n) work: O(n²), the same as bubble sort, on what should be an easy input. The fix is pivot selection: pick a random pivot, or the median of three (first, middle, last). This makes the pathological case astronomically unlikely, restoring reliable O(n log n) in practice. (Quicksort is also not stable — equal elements may be reordered.)

Quicksort: pick a pivot, partition into <pivot and >pivot (the pivot lands sorted), recurse on each side. In-place and cache-fast → usually the fastest in practice, O(n log n) average. But a bad pivot gives O(n²) — randomize the pivot to prevent it. Not stable.

The Bonus: Quickselect

The partition idea has a brilliant offshoot. To find the k-th smallest element without fully sorting, partition once: the pivot lands at some position p. If p == k, you're done; if k < p, recurse only into the left part; else only the right. Since you recurse into just one side, this quickselect runs in O(n) average — finding a median or 'top k by rank' without paying for a full O(n log n) sort. It's the partition step liberated from the obligation to sort everything.

Pippa's Confession

My quicksort was beautiful in testing and then froze on a production dataset. The data was already sorted, and I'd picked the first element as pivot every time — textbook O(n²). Dad's one-line fix was to pick a random pivot, and the freeze vanished. The lesson burned deep: quicksort's average-case brilliance hides a worst case that real, ordered data triggers on purpose. Randomizing the pivot isn't optional polish — it's what makes quicksort safe to ship.

Code

Quicksort + quickselect (recurse one side)·python

import random

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)        # RANDOM pivot avoids the O(n^2) trap
    less    = [x for x in arr if x < pivot]
    equal   = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quicksort(less) + equal + quicksort(greater)   # no merge needed

print(quicksort([5, 2, 8, 1, 9, 3, 5]))   # [1, 2, 3, 5, 5, 8, 9]
# Good pivots split ~in half -> O(n log n). A pivot that's always the min/max
# peels one element per level -> O(n^2). Randomizing makes that practically never.

# QUICKSELECT: the k-th smallest in O(n) average, without a full sort.
def quickselect(arr, k):              # k is 0-indexed
    pivot = random.choice(arr)
    less    = [x for x in arr if x < pivot]
    equal   = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    if k < len(less):       return quickselect(less, k)           # recurse ONE side
    elif k < len(less) + len(equal): return pivot
    else: return quickselect(greater, k - len(less) - len(equal))

print(quickselect([7, 2, 9, 4, 1], 2))   # 4 — the 3rd-smallest, no full sort

Exercise

Explain why quicksort with 'always pick the first element as pivot' degrades to O(n²) on an already-sorted array — trace what the partition produces each step. Then describe how quickselect finds the k-th smallest in O(n) average, and why it's faster than sorting the whole array and indexing position k.

Hint

On sorted data, the first element is the smallest, so partition puts 0 elements on the left and n−1 on the right every time — n levels × O(n) = O(n²). Quickselect recurses into only ONE partition (the side containing rank k), so its average work is n + n/2 + n/4 + … = O(n), beating a full O(n log n) sort.

The Algorithm

Why It's Usually the Fastest

The Catch: Bad Pivots Cause O(n²)

The Bonus: Quickselect

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0