Quick sort
Partition around a pivot, recurse — fast on average, with a worst case to respect. · 8 min read
Quick sort is the workhorse behind many real-world sort implementations. Choose a pivot, rearrange so everything smaller sits to its left and everything larger to its right (the partition step), then sort each side the same way.
Interactive visualization: Quick sort with Lomuto partition — step through it frame by frame on this page.
The amber bar is the pivot. As the scan runs, smaller elements get swapped into the growing “less-than” region, and finally the pivot drops into its exact final position — it never moves again. That guarantee is what makes the recursion work.
Why average and worst differ
good pivot: splits into n/2 and n/2— Balanced ⟹ recurrence T(n)=2T(n/2)+O(n).⟹ O(n log n)— Same tree as merge sort.bad pivot: splits into 0 and n−1— e.g. sorted input, always picking the end.⟹ T(n)=T(n−1)+O(n) = O(n²)— The tree degenerates into a line.
Result: O(n log n) average · O(n²) worst
Practice: Kth Largest Element (Medium) — Find the k-th largest value (1-indexed) in an unsorted array.