Quicksort's worst case comes from lopsided partitions

If each pivot leaves one side almost empty, partition work can add up to O(n^2). Randomized pivots make consistently bad splits less likely, while preserving the same worst-case bound. Balanced splits give O(n log n) work.