The same template, with the work moved
By now the divide, conquer, combine template is familiar: split the input, solve the pieces recursively, glue the answers back together. In the last guide, merge sort split the list trivially — just cut it in half by position — and paid for sorting in the combine step, where merging two sorted halves costs O(n) work per level. Quicksort is the mirror image. It pays up front in the divide step and gets the combine step for free.
Here is the whole idea in one breath. Pick one element of the array and call it the pivot. Rearrange the array so that everything smaller than the pivot sits to its left, everything larger sits to its right, and the pivot lands exactly where it belongs in the final sorted order. That rearrangement is called partitioning. Now recursively quicksort the left part and the right part. When both come back sorted, the whole array is already sorted — nothing left to glue. The pivot was correct, the left is sorted, the right is sorted, so they simply abut.
Partitioning, walked through by hand
Partitioning sounds like it needs scratch space, but the classic trick does it in place with a single sweep. Take the last element as the pivot. Walk a finger from left to right; keep a second marker just behind the boundary of "stuff known to be smaller than the pivot." Every time the finger lands on an element less than the pivot, push the boundary forward by one and swap that small element into the smaller-region. When the finger reaches the end, swap the pivot into the boundary slot. One pass, O(n) comparisons, no extra array.
pivot = A[hi]; i = lo - 1 // i marks end of the 'smaller' region
for j = lo to hi-1: // j is the scanning finger
if A[j] < pivot:
i = i + 1
swap A[i], A[j]
swap A[i+1], A[hi] // drop pivot into its final slot
return i+1 // the pivot's indexTrace [3, 7, 1, 5, 2] with pivot 2 (the last element). The finger sees 3 (not smaller, skip), 7 (skip), 1 (smaller! the boundary advances to index 0 and we swap A[0] with this 1 — the front element 3 is displaced to index 2, giving [1, 7, 3, 5, 2]), 5 (skip). The finger ends; we swap the pivot 2 into the boundary slot A[1], which sends the 7 to the end, giving [1, 2, 3, 5, 7]. Notice what we have: 1 is left of 2, and {3, 5, 7} are right of 2 — here they happen to be in order, but in general they need not be, only correctly on the right side. The pivot 2 is now in its final resting place forever, and we recurse on [1] and on [3, 5, 7].
Why is this correct? Because of a loop invariant that holds at every step of the sweep: everything in A[lo..i] is strictly less than the pivot, and everything in A[i+1..j-1] is at least the pivot. Each iteration restores this for the new element, so when the loop ends the array is cleanly split, and the final swap drops the pivot exactly on the seam. We are reusing the invariant machinery from earlier rungs — partitioning is not magic, it is a tiny loop with a provable promise.
Why the combine step costs nothing
This is the part that surprises people coming from merge sort. After both recursive calls return, quicksort does no combining at all — there is no merge, no copy, no comparison. The reason is that partitioning already placed every element on the correct side of the pivot, and the pivot itself is already final. So once the left subarray is internally sorted and the right subarray is internally sorted, concatenating them (which is free, since they are already adjacent slices of the same array) yields a fully sorted array. The combine step has collapsed to nothing.
So the O(n) per level that merge sort spends merging, quicksort spends partitioning instead — same budget, different step. If the pivot splits the array into two roughly equal halves, the recursion has about log n levels, each doing O(n) partition work, giving the now-familiar recurrence T(n) = 2 T(n/2) + O(n), which solves to O(n log n). The picture is identical to merge sort's recursion tree: O(n) work spread across about log n levels. Quicksort just reached it through a different door.
The pivot decides everything
Everything above assumed the pivot splits the array roughly in half. But nothing forces a good split — the pivot is just whatever element we picked, and the data decides how lopsided the result is. Suppose we always take the last element as pivot and the array is already sorted: [1, 2, 3, 4, 5]. The pivot 5 is the largest, so the left part gets all four other elements and the right part gets nothing. Partitioning still cost O(n), but it bought us almost no division. Next level: pivot 4 is again the largest of what remains, and again everything piles onto one side.
Now the recurrence is not T(n) = 2 T(n/2) + O(n) but T(n) = T(n-1) + O(n): one subproblem barely smaller than the last, peeling off a single element at a time. That recursion has n levels, not log n, and level k still does about n-k partition work. Summing 1 + 2 + ... + n gives Theta(n^2). The very same algorithm that ran in O(n log n) on a lucky pivot runs in O(n^2) on an unlucky one — a quadratic blowup, and on already-sorted input, of all things, which is exactly the case you might naively expect to be easy.
This is the central honesty about quicksort, and it maps straight onto the worst/best/average lens from the foundations rung. Its best and average case are O(n log n), but its worst case is genuinely Theta(n^2). Quoting only the average — "quicksort is an n log n algorithm" — hides a real cliff. And the cliff is reachable not by adversarial gibberish but by ordinary, sorted-or-nearly-sorted data, which shows up in the real world all the time.
Randomizing the pivot: trading a guarantee for luck
The fix is beautiful and a little sneaky. Instead of always taking the last element, pick the pivot uniformly at random from the current subarray. This is randomized quicksort. Crucially, it does not make any single input safe — for any fixed pivot rule there is still some input that triggers Theta(n^2). What randomization changes is who controls the bad case. The split is now decided by your coin, not by the data's order, so no particular input — not sorted, not reversed, not anything an adversary hands you in advance — can reliably force the worst case.
- Before partitioning a subarray, pick a random index in it and swap that element to the end, so the pivot is a uniformly random one of the elements present.
- Partition exactly as before. Because the pivot is random, the chance it lands somewhere reasonably central — giving a not-too-lopsided split — is high.
- Recurse on both sides. Over the whole run, a careful expectation argument (one indicator per pair of elements, summed by the linearity of expectation) shows the expected number of comparisons is about 1.39 n log n.
That expected bound leans on a tool worth naming: the linearity of expectation. You define, for each pair of elements, an indicator that is 1 if they ever get compared, work out the probability of that (it turns out to be 2/(distance+1) in sorted order), and add up all the tiny expectations — even though the events are tangled and dependent, the expected sum is just the sum of expectations. That trick converts a frightening web of recursive randomness into a clean, addable total of O(n log n).
Choosing well, and what quicksort is really for
Randomizing is not the only defense. A common deterministic heuristic is median-of-three: look at the first, middle, and last elements and use their median as pivot. It cheaply dodges the already-sorted disaster and tends to give balanced splits in practice, though a clever adversary who knows the rule can still construct a Theta(n^2) input — a deterministic rule can always be fooled in principle. The deepest fix, choosing a provably good pivot in linear time using the median-of-medians, is the subject of guide 5 in this rung; it removes the worst case entirely, at the cost of a larger constant.
Why use quicksort at all, given that merge sort guarantees O(n log n) with no asterisk? The honest answer is constants and memory. Quicksort partitions in place, needing only O(log n) stack space, while textbook merge sort copies into an auxiliary array of size n. And its inner loop is tight and cache-friendly, so its hidden constant is small — this is the hidden constant biting in quicksort's favor for once. In practice randomized quicksort is often the fastest comparison sort, which is precisely why asymptotics alone never settle a choice; you weigh the worst-case guarantee against the typical speed.
One more honest note about the ceiling. Like merge sort, quicksort is a comparison-based sort, and no comparison sort can beat the Omega(n log n) lower bound in the worst case — so n log n is not a quirk of these two algorithms but a wall the whole comparison model runs into. Finally, the same partition idea, used to recurse into only one side instead of both, gives linear-time selection (finding the k-th smallest element); that is the quickselect cousin you will meet in guide 5, and it is yet another payoff of mastering partitioning here.