Quicksort

Summary

Quicksort is a divide-and-conquer sorting algorithm. It picks a pivot element, partitions the other elements into those smaller and those not smaller than the pivot, and sorts the two parts recursively. Its worst case is $\Theta(n^2)$ comparisons, but with a uniformly random pivot the expected number is about $2 n \ln n \approx 1.39\, n \log_2 n$, and it is very fast in practice.