Recap: Quicksort

Partition, recurse into each side, choose the pivot at random, and keep the stack shallow.

Quicksort sorts by partitioning around a pivot and sorting each side, which makes it fast on average, slow on the inputs a badly chosen pivot meets, and the basis of quickselect. This card gathers what the topic established and where each idea was taught.

What the topic established, and which card it was on
The idea	Where
A partition puts the pivot in its final place, smaller items left and the rest right, so no merge is needed	Quicksort: Partition Around a Pivot, Then Sort Each Side
Lomuto's scan swaps each smaller item to index i, then swaps the pivot into i	Partition an Array With the Lomuto Scheme
A last-item pivot is quadratic on sorted, reversed and all-equal input; a random pivot fixes the first two	Taking the Last Element as Pivot on Sorted Input
Recursing into the smaller side and looping over the larger caps the stack at about log₂ n	Keeping the Stack Shallow by Recursing Into the Smaller Side
A practical quicksort swaps a random pivot to the end and loops over the larger side	Quicksort in Python, Java and TypeScript
Hoare's scheme swaps less and splits equal keys evenly; a three-way partition finishes them	Lomuto vs Hoare Partitioning
Keeping only the side that holds index k − 1 finds the k-th smallest in expected O(n)	Quickselect: Partitioning to Find the k-th Smallest
A median of nine times took three partitions and 12 comparisons	Practice: Finding the Median Delivery Time

Quicksort and quickselect on n items

Quicksort, average case: O(n log n); random pivot, on any input
Quicksort, worst case: O(n²); every pivot the largest or smallest of its range
Stack depth: At most about log₂ n; recursing into the smaller side
Stable: No; swaps carry items past equal ones
Quickselect, average case: O(n); random pivot; n + n/2 + … stays below 2n
Quickselect, worst case: O(n²); the same pivots that make quicksort quadratic

Quicksort's speed depends on its pivots in a way merge sort's does not depend on anything, and every practical detail in this topic is about choosing them well or limiting the damage when they are chosen badly. Choosing a Sorting Algorithm, a later topic, sets quicksort against merge sort, heapsort and the built-in sorts.

← → move through sections and cards