Quicksort
A divide-and-conquer sorting algorithm selecting a pivot and partitioning elements around it. Quicksort averages O(n log n) with small constants, making it practically fastest for many datasets. Worst case O(n²) on sorted input and poor pivot selection.
Formula
Average case: O(n log n); Worst case: O(n²)
Real World
The C standard library's qsort function, used in millions of programs from video games to banking software, implements quicksort with randomised pivot selection to avoid the O(n²) worst case on real-world data.
Exam Focus
Explain why sorted input causes worst case — unbalanced partitions — and how random pivot selection mitigates it.
How well did you know this?