- Divide and conquer
- Select a pivot point, move items smaller than pivot point value to the left of pivot point and items large than pivot to the right.
- Pick a new pivot point and repeat until sorted.
- Closely related to Quick Select – which allows us to find the kth smallest/largest item.
Picking a Pivot
- Take the first, middle and last element and pick the median as a pivot.
In place, not considering call stack
In the worst case, if you make bad pivots takes n^2 run time