Algorithms / Quicksort Partition
Least You Need to Know: Quicksort Partition Intuition and Pivot Invariants
Quicksort relies on a partition step that rearranges elements around a pivot so recursive calls can sort the left and right sides independently. The key reasoning tools are pivot invariants, the role of balanced partitions in expected speed, and the fact that unlucky pivots can still create quadratic worst-case behavior.
The least you need to know
- Partitioning places elements smaller than the pivot on one side and larger ones on the other, according to the chosen convention.
- After partitioning, the pivot is in a position consistent with its final sorted rank.
- Balanced partitions make quicksort fast on average; highly unbalanced partitions cause bad recursion depth.
- Poor pivot choices can lead to worst-case `O(n^2)` behavior.
- Three-way partitioning helps when many duplicate keys are present.
Key notation
pivot
the chosen element used to split the array
partition invariant
a maintained statement about which region contains smaller, equal, or larger elements
three-way partition
split into `< pivot`, `= pivot`, and `> pivot` regions
Tiny worked example
- Choose a pivot.
- Reorder the array so smaller elements go left and larger elements go right.
- Once partition finishes, the pivot has the correct relative position between the two sides.
- Then recurse on the left and right subarrays.
Common mistakes
- Students often say partition 'sorts' the whole array, but it only enforces a pivot-centered invariant.
- Expected speed comes from typical partition balance, not from a worst-case guarantee.
- Duplicate-heavy inputs are a good reason to remember three-way partitioning.
How to recognize this kind of problem
- The prompt emphasizes pivots, left/right regions, or partition loops.
- The key proof idea is an invariant over indices during partition.
- Average-case versus worst-case recursion shape is central.