Worst-Case Analysis: Already Sorted Input
What you'll learn: Why Quicksort can degrade to O(n²) performance when the input is already sorted and a poor pivot choice is made.
The Problem with Sorted Data
Remember how Quicksort's efficiency depends on balanced partitions? When your input is already sorted (like [1, 2, 3, 4, 5]) and you consistently choose a bad pivot—say, always picking the first or last element—disaster strikes.
Here's why: If you pick the first element as pivot in a sorted array, the partition operation puts everything else on one side. You get a "partition" of 0 elements and n-1 elements. Then you recurse on that n-1 subarray, pick its first element, and again get an unbalanced split of 0 and n-2 elements.
The Cascade Effect
Instead of dividing the problem in half each time (which gives us O(n log n)), we're only reducing it by one element per recursive call. This creates a recursion tree with O(n) levels instead of O(log n) levels. At each level, we still do O(n) work for partitioning.
O(n) levels × O(n) work per level = O(n²) total time
Real-World Analogy
Imagine organizing a tournament bracket where you always match the strongest player against all others at once instead of pairing them evenly. You'd end up with n-1 sequential rounds instead of log n elimination rounds—taking much longer to finish.
This is why pivot selection strategies (like median-of-three or randomization) are crucial. They help avoid this worst-case scenario, especially when data might already be partially or fully sorted.
Key Takeaway: When Quicksort consistently makes poor pivot choices on sorted (or reverse-sorted) data, it degrades from O(n log n) to O(n²) by creating maximally unbalanced partitions at every recursive level.