Quicksort & Partitioning

The partition step, reused

Module 10's Partition Pointers lesson built exactly the function quicksort needs: rearrange an array in place so everything less than a pivot comes before everything greater — the write-pointer partition template, with pred = "less than the pivot":

def partition(arr: list[int], lo: int, hi: int) -> int:
    pivot = arr[hi]                    # choose the last element as pivot
    boundary = lo                       # arr[lo:boundary] < pivot
    for i in range(lo, hi):
        if arr[i] < pivot:
            arr[boundary], arr[i] = arr[i], arr[boundary]
            boundary += 1
    arr[boundary], arr[hi] = arr[hi], arr[boundary]   # pivot lands at boundary
    return boundary                     # pivot's FINAL sorted position

The key fact partition delivers: after it runs, the pivot sits at its correct final position in the fully sorted array — everything to its left is smaller, everything to its right is larger. That's enough to sort recursively: partition, then recursively sort the two sides independently, never touching the pivot again.

Trace it on arr = [8, 3, 7, 1, 5], pivot arr[4] = 5, boundary = 0: i=0 (8): 8 < 5? No — no swap, boundary stays 0. i=1 (3): 3 < 5? Yes — swap arr[0] and arr[1]: [3, 8, 7, 1, 5], boundary → 1. i=2 (7): no swap. i=3 (1): 1 < 5? Yes — swap arr[1] and arr[3]: [3, 1, 7, 8, 5], boundary → 2. Loop ends; final swap arr[2] and arr[4]: [3, 1, 5, 8, 7]. The pivot 5 sits at index 2 — everything left (3, 1) is smaller, everything right (8, 7) is larger, exactly as promised, in one linear pass.

Think of it like a queue of people of different heights, with one person picked as the reference height: walk the line once, pulling anyone shorter than the reference to the front of a growing "shorter" group as you pass them — by the time you reach the end, the reference person can step directly into the one gap that's neither too far forward nor too far back.

Quicksort itself

def quicksort(arr: list[int], lo: int = 0, hi: int | None = None) -> None:
    if hi is None:
        hi = len(arr) - 1
    if lo < hi:
        p = partition(arr, lo, hi)
        quicksort(arr, lo, p - 1)        # everything smaller than pivot
        quicksort(arr, p + 1, hi)        # everything larger than pivot

Sorting happens entirely IN PLACE — no merge step, no auxiliary array (unlike merge sort). This is quicksort's headline advantage: better constant factors and O(log n) auxiliary space (the recursion stack) instead of merge sort's O(n).

The case split you already know how to reason about

The Big O module's best/worst/average lesson used quicksort as its worked example, in the abstract. Now you have the actual partition code to reason about directly:

Worst case: Θ(n²). If partition always picks a pivot that splits the array into sizes 0 and n−1 (e.g., choosing the last element as pivot on an already-sorted array — every element compares against a pivot that's the current maximum, so nothing ever goes right), the recursion degenerates into a straight chain, n levels deep, doing O(n) partition work at each level: n × n = n².

Average case: Θ(n log n). With a randomly chosen pivot, bad splits become vanishingly unlikely for any fixed input — the randomness is in the algorithm's own coin flips, not an assumption about "typical" data. This is Big O's "average case" done honestly: not "assume nice input," but "the algorithm defends itself against ALL input via its own randomization."

randomized pivot choice (swap a random index into the pivot slot first):

import random

def partition_randomized(arr: list[int], lo: int, hi: int) -> int:
    r = random.randint(lo, hi)
    arr[r], arr[hi] = arr[hi], arr[r]     # randomize which element is "last"
    return partition(arr, lo, hi)          # then partition exactly as before

One line — swap a random element into the pivot slot before running the same deterministic partition — converts "fails on adversarial input" into "expected O(n log n) on EVERY input," because no fixed input can reliably trigger bad splits against a pivot the algorithm itself chose unpredictably.

Stability, and why quicksort gives it up

The partition step's swap (arr[boundary], arr[i] = arr[i], arr[boundary]) can move an element PAST an equal element it was originally behind — quicksort is not stable. This is the direct cost of the same trade the Partition Pointers lesson named back in Module 10: swap-based partitioning buys in-place, O(1)-auxiliary rearrangement at the price of order-within-groups. Merge sort spent O(n) space to keep that order; quicksort spends none, and loses it.