Quicksort and Randomized Quicksort

Quicksort is the sorting algorithm most language standard libraries have historically defaulted to (C's qsort, and the core of many hybrid sorts), because its expected running time is $\Theta(n\log n)$ with a small constant and it sorts in place — yet its worst-case running time is $\Theta(n^2)$, and that worst case is triggered by exactly the kind of already-sorted or adversarially-crafted input a naive deployment might see. This note derives both bounds, shows precisely how randomization — first introduced as a design principle in Topic 1 — converts the dangerous worst case into a vanishingly unlikely event regardless of the input, and proves the $O(n\log n)$ expected bound using the same indicator-variable technique built there.