Quicksort

By the end of this lesson you will be able to trace partitionLomuto and quicksort by hand, explain exactly why quicksort is Θ(n²) in the worst case but Θ(n lg n) on average, implement the randomized version and three classic variants (Hoare's partition, three-way partitioning, bounded stack depth), and answer interview questions that build on the same partitioning idea (Dutch-flag sort, quickselect, and more). Every array in this lesson is 0-indexed, exactly like the Dart code, and lo..hi always means an inclusive range of positions.

1. The idea: divide, partition, conquer

Quicksort is a divide-and-conquer algorithm, like merge sort — but where merge sort does the hard work in the combine step (merging two sorted halves), quicksort does all its hard work in the divide step, and the combine step is free. To sort the range a[lo..hi]:

• Divide — rearrange (partition) the range around one element, the pivot, which ends at some index q: everything in a[lo..q-1] is ≤ a[q] and everything in a[q+1..hi] is ≥ a[q]. The pivot is now in its final sorted position.
• Conquer — recursively sort the two smaller ranges a[lo..q-1] and a[q+1..hi].
• Combine — do nothing! Everything left of q is already ≤ everything right of q, so once the two sides are individually sorted the WHOLE array is sorted.

Quicksort sorts in place (only a constant number of values are ever stored outside the array, apart from the call stack) and, despite a Θ(n²) worst case, is usually the fastest general-purpose comparison sort in practice — small constants and good cache behavior, because it scans memory in order.

2. Lomuto partition — the workhorse subroutine

The version below is named after Nico Lomuto. It always takes the last element of the range, a[hi], as the pivot, and keeps one index i marking the end of the "≤ pivot" region:

The loop invariant — a fact that is true every time the for loop (row 3) is about to start an iteration — is what makes the procedure provably correct. For the current loop index j:

• a[lo..i] ≤ pivot (the "≤ pivot" region — green above)
• a[i+1..j-1] > pivot (the "> pivot" region — red above)
• a[hi] = pivot (parked at the end — blue above)
• a[j..hi-1] is unrestricted — not yet examined (grey/dim above)

Before the first iteration: i = lo-1 and j = lo, so the first two regions are empty — trivially true. Each iteration keeps it true: either (a) a[j] > pivot, so the "> pivot" region simply absorbs a[j] (nothing to move), or (b) a[j] ≤ pivot, so we increment i and swap a[i] with a[j] — the OLD a[i] (the first element of the "> pivot" region) goes to the end of that region, while a[j] becomes the new last element of the "≤ pivot" region. When the loop ends: j = hi, so the unrestricted region is empty and every element except the pivot has been classified — exactly what we need before swapping the pivot into place.

In Dart: the loop invariant checked at the top of every iteration on the first example (lo = 0, hi = 7).

The Dart implementation

The pseudocode above and this code use the same indices: the range is lo..hi (inclusive) and the pivot is simply a[hi].

In Dart: partitioning n = hi − lo + 1 elements makes exactly n − 1 comparisons, i.e. Θ(n): 9, 99 and 999 comparisons for n = 10, 100 and 1000.

3. Quicksort and the loop invariant

quicksort(a, 0, a.length − 1) sorts the whole array. If lo ≥ hi the range has 0 or 1 elements — already sorted, nothing to do (the base case).

The Dart implementation

4. Performance: worst case, best case, balanced splits

Worst case — Θ(n²): partitioning returns the most unbalanced split possible, sizes 0 and n-1, at every single call. This happens whenever the input is already sorted (ascending OR descending) and the pivot is always the largest or smallest remaining element. The recurrence is T(n) = T(n-1) + T(0) + Θ(n) = T(n-1) + Θ(n), which unrolls to Θ(n) + Θ(n-1) + … + Θ(1) = Θ(n²) — an arithmetic series, exactly like the worst case of insertion sort.

In Dart: the worst-case recurrence T(n) = T(n−1) + n as a recursive function, its closed form n(n+1)/2, and the real comparison count n(n−1)/2 of quicksort on a sorted array.

Best case — Θ(n lg n): partitioning always splits as evenly as possible, sizes ⌊(n−1)/2⌋ and ⌈(n−1)/2⌉. The recurrence is T(n) = 2T(n/2) + Θ(n) — master theorem case 2, giving Θ(n lg n), matching merge sort.

In Dart: the best-case recurrence T(n) = 2T(n/2) + n for n = 2^k against its closed form n lg n + n.

Balanced-split intuition (the key insight that makes randomization work): you don't need an EXACTLY even split to get Θ(n lg n) — any constant proportion split works. Even a lopsided 9-to-1 split gives T(n) = T(9n/10) + T(n/10) + cn. The recursion tree for this still only has depth Θ(lg n) (each branch shrinks by a constant factor every level, so it takes log_{10/9} n levels down the "9/10" side to hit size 1 — still Θ(lg n), just with a bigger constant), and every level costs at most cn, so the total is still O(n lg n). Even a 99-to-1 split is Θ(n lg n) — only the constant factor gets worse, never the asymptotic order. This is exactly why randomized quicksort (next section), which makes no promise of an even split but does avoid always picking the worst one, still runs in expected Θ(n lg n).

In Dart: the 9-to-1 recurrence T(n) = T(9n/10) + T(n/10) + n with a memo table, and the number of levels on the deep side (about log_10/9 n, still Θ(lg n)).

5. Randomized quicksort

Instead of always using a[hi] as the pivot, first swap a uniformly random element of a[lo..hi] into position hi, then run the ordinary Lomuto partition.

This changes the running time from a property of the input to a property of the random choices made — no particular array (not even a fully sorted one) can force worst-case behavior on every run, and the expected running time over the algorithm's own coin flips is Θ(n lg n) for ANY input, proven in the next section.

The Dart implementation

6. Analysis: why the expected time is Θ(n lg n)

Worst case is still Θ(n²): even randomized, SOME sequence of coin flips could always draw the worst pivot; substituting T(n) ≤ cn² into the max-recurrence T(n) = max0≤q≤n-1[T(q) + T(n-1-q)] + Θ(n) and noting q² + (n-1-q)² is maximized at the endpoints (q=0 or q=n-1) confirms O(n²), matching the Ω(n²) lower bound from the deterministic worst-case example — so the worst case is exactly Θ(n²), it's just astronomically unlikely.

In Dart: the worst-case recurrence T(n) = max_q[T(q) + T(n−1−q)] + n computed by brute force over every split q: the maximum is always at an endpoint, so it equals n(n+1)/2.

Expected case is Θ(n lg n) — the heart of the lesson. Rename the elements in sorted order z1 < z2 < … < zn (the subscript is the element's rank, counting from 1), and let X be the TOTAL number of times the test a[j] ≤ pivot is ever evaluated across the entire run. Cost fact: the running time of quicksort is O(n + X) (at most n calls do any partitioning, each doing O(1) work plus exactly one comparison per loop iteration).

In Dart: the cost fact: counting the calls that reach the partition (at most n − 1) and X, the total number of comparisons.

The key trick is an indicator random variable for every PAIR (zi, zj) with i < j: define Xij = I{zi and zj are ever compared}. Then X = Σi<j Xij, and by linearity of expectation, E[X] = Σi<j Pr{zi and zj are compared} — no independence needed, linearity always holds.

The crucial observation: once a pivot is chosen that lies STRICTLY BETWEEN zi and zj in value, they end up in different ranges forever and are NEVER compared to each other again. So zi and zj are compared if and only if one of them is the very FIRST pivot ever chosen from the set Zij = {zi, zi+1, …, zj} (which has j-i+1 elements). Since every element of Zij is equally likely to be the first one picked as a pivot from that set, Pr{zi compared to zj} = 2/(j-i+1) (the "pair rule").

In Dart: estimating Pr{z_i and z_j are compared} by running randomized quicksort 20 000 times on the sorted values 0..7 (value k−1 is the element of rank k); the code also throws if any pair is ever compared twice.

Substituting and summing (change of variable k = j - i) turns the double sum into a sum of harmonic series, giving E[X] = Σk=1..n−1 (n−k)·2/(k+1) = 2(n+1)Hn − 4n = O(n lg n) — combined with the Ω(n lg n) best-case lower bound, the expected running time of randomized quicksort is Θ(n lg n), for ANY input.

In Dart: the pair sum, the gap sum and the closed form 2(n+1)H_n − 4n, plus the 2n ln n leading term from the table below (n = 200: 1563.0 vs 2119.3; n = 1000: 10985.9 vs 13815.5).

The measured column comes from running randomized quicksort (with a fixed seed for reproducibility) many times and counting every comparison the partition loop makes, then averaging — it lines up almost exactly with the exact combinatorial formula E[X] = Σi<j 2/(j-i+1). The simpler "2n ln n" figure is only the leading term of that exact sum as n → ∞ — at these finite sizes it's a real overestimate (26–36% high here), though the ratio does shrink toward 1 as n grows, since the lower-order corrections become relatively smaller.

7. Hoare's original partition

hoarePartition picks the FIRST element, a[lo], as the pivot (not the last), and uses two indices that scan inward from both ends. Each one always takes at least one step before it starts testing:

The Dart implementation

In Dart: checking the Hoare postcondition a[lo..j] ≤ a[j+1..hi] (with lo ≤ j < hi) on the page's 10-element array, which is exactly what makes the recursion on (lo, j) and (j+1, hi) correct.

8. Three-way partitioning (many duplicates)

Here is the standard one-pass solution. It keeps three markers lt, i and gt that split the range into four zones: < pivot, == pivot, not yet examined, and > pivot:

The Dart implementation

In Dart: counting the work on an all-equal array: Lomuto quicksort does n(n−1)/2 comparisons, the three-way version makes one pass of n steps (n = 10, 100, 1000).

9. Bounding the stack depth

A first improvement turns one of the two recursive calls into a while-loop update — a genuine tail call (the very last thing the function does), which reuses the CURRENT stack frame instead of pushing a new one. But by itself, always recursing on the left piece and looping on the right (without choosing) can STILL hit Θ(n) stack depth on adversarial input — the fix is to always make the genuine recursive call on the SMALLER piece and loop (tail-call) on the LARGER one. The panel below shows both: rows 1–5 are leftRecursiveQuicksort (the naive loop version), rows 7–15 are boundedStackQuicksort (the fix):

The Dart implementation

In Dart: leftRecursiveQuicksort (rows 1–5), measuring its recursion depth: on a sorted array of n = 64 it reaches n − 1 = 63.

In Dart: the fix (rows 8–15):

In Dart: recursing only on the smaller side and looping on the larger: the maximum depth stays ≤ ⌊lg n⌋ even on a sorted array, where the left-recursive version reaches n − 1.

10. Median-of-three pivots

Sample 3 elements uniformly at random (without replacement) from the n elements and use their median as the pivot. This is a real, runnable algorithm — not just theory — so here it is in action, using the exact same Lomuto machinery from section 2 once the median-of-three pivot has been chosen and swapped into place:

The Dart implementation

Let s1 < … < sn be the elements in sorted order (subscript = rank, counting from 1), and let pi = Pr{the pivot turns out to be si}. For the pivot to land EXACTLY on rank i, the sample of 3 needs exactly one element ranked below i, one ranked above, and one AT rank i itself:

pi = C(i-1,1)·C(n-i,1) / C(n,3) = 6(i-1)(n-i) / (n(n-1)(n-2)), for 2 ≤ i ≤ n-1 (and p1 = pn = 0 — the extreme ranks can never be the median of 3 distinct samples).

In Dart: the formula p_i = 6(i−1)(n−i) / (n(n−1)(n−2)) (rank i counts from 1, so the list index is i−1) next to a brute-force count over all 84 triples for n = 9, which reproduces the table above.

Exactly as the formula predicts: probability rises smoothly toward the true middle rank and is symmetric — and the extreme ranks 1 and 9 are impossible, unlike ordinary random-pivot selection where every rank (including the extremes) is equally likely at probability 1/9 ≈ 0.111.

The limiting ratio: as n → ∞, compare pi at the exact middle rank against the ordinary single-random-pivot probability 1/n. For n = 99, exact middle rank i = 50: p50 = 0.015308 versus ordinary 1/99 = 0.010101 — a ratio of 1.515, already very close to the limiting ratio of 3/2 at n = 99 (both numbers verified in verify/c07.dart).

In Dart: the ratio p_(n+1)/2 / (1/n): 1.515 at n = 99 and 1.5000015 at n = 1 000 001.

"Good split" probability: define a split as "good" if the pivot's rank lands in the middle third, [n/3, 2n/3]. Integrating pi over that range (as n → ∞) shows median-of-3 lands in the good range with probability 13/27 ≈ 0.4815, noticeably more often than ordinary random sampling's flat 1/3 chance.

In Dart: summing p_i over the middle third for n = 3000 gives ≈ 0.4815 (= 13/27), against ≈ 1/3 for a uniform pivot.

Quiz

Interview questions

Cheat sheet