Partitioning around a pivot
One two-way partition scans from both ends for items on the wrong side of a chosen pivot and exchanges them. Once scans cross, the pivot is placed between regions satisfying the relevant ordering relation. Neither region is necessarily internally sorted yet.
Recursive calls then sort the two sides. Correctness requires the partition invariant and strictly smaller recursive ranges. Mishandling the positioned pivot or scan boundaries can prevent progress on extreme or repeated keys.
References: [1]
Expected work differs from the worst case
Roughly balanced partitions distribute linear scans over logarithmically many levels, yielding O(n log n) work. Repeatedly removing only one item instead gives O(n²). A naive fixed-first pivot can encounter this pattern on sorted input.
Shuffling first or choosing random pivots gives expected O(n log n) cost under the corresponding randomness model. It does not guarantee logarithmic depth for every random outcome. Recursion-stack behavior remains an implementation concern.
References: [1]
Handling repeated keys
Three-way partitioning separates keys smaller than, equal to and greater than the pivot. The equal region needs no recursive sorting, reducing repeated work when duplicates are common. Two-way implementations still need careful equal-key and termination rules.
Ordinary in-place swapping is generally unstable. Implementations can combine small-range insertion sort or other pivot rules. Partitioning also supports rank selection, which locates a requested kth item without promising a fully sorted array.