Quicksort & Partitioning

Quicksort is another divide-and-conquer sort, but where merge sort splits the array blindly down the middle and does its real work while merging, quicksort does the opposite: it does the real work up front (partitioning), and the recursive calls on the resulting pieces need no merge step at all - once every element is on the correct side of the pivot and the two sides are each sorted, the whole array is sorted.

Pick one element as the pivot, then rearrange the array so everything less than or equal to the pivot ends up to its left, and everything greater ends up to its right. The pivot is now in its final sorted position - it never needs to move again. Recursively partition the left and right sub-ranges the same way, and the base case (a range of size 0 or 1) is already sorted.

When the pivot happens to land near the middle of its range, each partition splits the problem roughly in half, and you get the same O(n log n) shape as merge sort - but without merge sort's extra O(n) space, since partitioning happens in place. The trouble is what happens when the pivot is consistently the smallest or largest element in its range: the "split" becomes one side of size n-1 and the other of size 0, and the recursion depth becomes O(n) instead of O(log n), producing O(n²) total work. The classic trigger is an already-sorted (or reverse-sorted) array combined with always picking the last element as the pivot - every partition is maximally lopsided.

• -Picking a random pivot, or the median of the first/middle/last elements, makes the worst case astronomically unlikely on real-world data, even though a pathological worst case technically still exists.
• -Quicksort is in-place (O(log n) stack space from recursion, no extra output array), which is why it tends to beat merge sort in practice despite the same average time complexity.
• -Quicksort is not stable by default - equal elements can end up reordered relative to each other during partitioning.

Production language runtimes rarely ship one pure textbook algorithm. Python's built-in `sorted()` and `list.sort()` use Timsort, a hybrid that finds already-sorted "runs" in the data and merges them (borrowing from merge sort's guaranteed-worst-case idea), while falling back to insertion sort for small runs (borrowing from Chapter 1, since insertion sort's low overhead wins at small sizes). Many C/C++ standard library sorts similarly combine quicksort's speed with a fallback to heap sort to cap the worst case, and a switch to insertion sort at small sizes. The lesson is not "one algorithm is best" - it is that different algorithms win in different regimes, and production code exploits that instead of picking a single favorite.