Quicksort
= Quicksort
A <divide-and-conquer algorithm> that partitions entries relative to a pivot, recursively sorts the smaller and larger partitions, and combines their results. A three-way partition keeps all equal keys in a central bucket. Correctness follows from the partition order and recursive correctness; excluding the pivot from child inputs provides decreasing finite lengths. The choice of pivot controls balance and therefore running time.