Quick Sort Process

1. Select a pivot point p
2. Move all smaller elements to the left of p
3. Move all larger elements to the right of p
4. Recurse on both left and right sides

Quick Sort Runtime

• Worst-case: θ(n²) - when all chosen pivots are the min/max

• Average-case:

  Average-Case & Amortized Analysis