Problem
Implement a sorting algorithm and discuss its complexity.
A. Quicksort
Implement quicksort in place. What is its average-case and worst-case time complexity? How do you choose the pivot to avoid the worst case?
B. Comparison sort lower bound
Prove that any comparison-based sort requires comparisons in the worst case.