# Quicksort - Worst case $\Theta(n^2)$, average $\Theta(n\lg n)$ with a small constant factor. - Steps - **Divide:** `A[p:r]` into `A[p:q-1]` (low side) and `A[q+1:r]` (high side), so that `all(a <= A[p] for a in A[p:q-1]) and all(A[p] <= a for a in A[q+1:p])` - **Conquer**: sort the two subarrays - **Combine** by doing _nothing_. - The key to the algorithm is `partition` procedure, which always chooses `A[r]` as the pivot, and classify the other elements. - Choosing a good pivot to divide the array into roughly equal half is the key - Middle element - Median of three (first, middle, last) - Random pivot