Quicksort

Partition around a pivot: smaller left, larger right. Recurse into each side. In place, no merge.

Partition is the operation

• Pick a pivot; sweep; small elements swap left of a boundary
• Pivot lands in its final sorted position
• Recurse into the two sides
• O(n log n) average, in place — usually the fastest sort

Watch the partition

Purple pivot · yellow compares · blue = smaller · green = placed.

The pivot is everything

Last-element pivot on sorted input = O(n²). 141× slower at n=4000.

Tame the worst case

• Randomize the pivot → the bad case essentially never happens
• Or median-of-three, or introsort (fall back to heapsort)
• Never ship a fixed-position pivot

Takeaway

Fastest in-place sort — if you guard the pivot. Avg O(n log n), worst O(n²). Next: heapsort — O(n log n) guaranteed AND in place.