Quicksort

Quicksort is a divide-and-conquer sort. It picks a pivot, partitions the array so smaller elements go left and larger go right, then recursively sorts each side.

Average time is O(n log n).

The key idea is partitioning: rearrange the array around a pivot so that everything left of the pivot is smaller and everything right is larger. The pivot then sits in its final sorted position.