The heart of quicksort
Quicksort picks a pivot, partitions the array so smaller values go left and larger go right, then recurses into each side. The pivot lands in its final position. Everything rests on how the partition step is written.
Lomuto scheme
- Uses one scanning pointer plus a boundary marking the end of the smaller region.
- Walks the array once, swapping any element below the pivot into the smaller region, then drops the pivot in place.
- Simple to reason about, but it performs more swaps and behaves poorly when many keys are equal.
Hoare scheme
- Uses two pointers that move inward from both ends and swap pairs found on the wrong side.
- Does fewer swaps on average and handles repeated keys more gracefully.
- Returns a split point rather than the pivot's final index, which changes how recursion is set up.
Pivot choice and worst cases
- A fixed pivot on sorted input gives lopsided splits and a slow worst case.
- Randomized pivots or a median of three sample keep splits balanced in practice.
- Recursing into the smaller side first bounds the stack depth.
Key idea
Quicksort's speed lives in its partition: Hoare swaps less than Lomuto, and randomized or median pivots keep the splits balanced and the worst case rare.