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