On this page

Quick Sort, Partition Schemes & Introsort

Quicksort is the sort most standard libraries reach for when stability is not required, and the one most programmers get subtly wrong when they write it themselves. The idea fits in one sentence — pick a pivot, put the smaller elements to its left and the larger to its right, recurse on both sides — but the details decide whether it runs in comparisons or , whether it uses stack or overflows it, and whether an attacker can make your server spend minutes sorting a few thousand items. This lesson takes each detail seriously: two partition schemes with their invariants and their traps, three-way partitioning for duplicate keys, pivot selection, the expected-case proof, the worst case and how to provoke it on purpose, and the hybrid introsort that every major C++ standard library ships.

Lesson position: Module 2 · Searching & Sorting · previous: Merge Sort & Inversion Counting · next: Heap Sort · course map.

Why this exists

Merge sort already sorts in worst case, so why does quicksort exist at all? Because merge sort needs a second array of elements and moves every element on every level of the recursion. Quicksort partitions in place: it needs only the stack, it touches memory in long sequential sweeps, and its inner loop is a compare, an increment and an occasional swap. On random data a well-engineered quicksort is typically one of the fastest comparison sorts on real hardware, and the comparison count is only about 39% above the information-theoretic minimum.

Tony Hoare invented the algorithm in 1959–1960, while a visiting student in Moscow working on machine translation: he needed to sort the words of a Russian sentence before looking them up in a dictionary stored on magnetic tape. He published it in 1961–1962. His two-index scheme is the original; the single-scan scheme most textbooks teach first is attributed to Nico Lomuto and was popularised by Bentley's Programming Pearls and CLRS. Sedgewick's 1975 thesis gave the precise average-case analysis.

Quicksort then spent four decades being hardened: three-way partitioning and the "ninther" pivot (Bentley and McIlroy, 1993), introsort (Musser, 1997), and McIlroy's 1999 proof that any deterministic quicksort can be driven quadratic. Today std::sort in libstdc++ and Microsoft's STL is an introsort, Java sorts primitive arrays with Vladimir Yaroslavskiy's dual-pivot quicksort, and Go and Rust have used Orson Peters's pattern-defeating quicksort (pdqsort) for their unstable sorts. The Sorting in the Real World lesson opens those libraries up; this lesson gives you everything you need to read their source.

Pattern triggers

If the problem says or has…Think of…
"sort in place", " extra space", "no extra array" and stability is not requiredQuicksort (or introsort / heapsort for a guaranteed bound)
"partition", "put all X before all Y", "rearrange around a value"One partition pass — Lomuto or Hoare — not a full sort
"three categories", "less / equal / greater", "sort colors", "many duplicates"Three-way (Dutch national flag) partition
"k-th smallest / largest", "median", "top k" without needing the rest sortedPartition once and recurse on one side: quickselect
"worst case must be ", "real-time", "adversarial input"Introsort, heapsort or merge sort — never a bare deterministic quicksort
"stable", "preserve the original order of equal elements"Not quicksort: merge sort or Timsort (Merge Sort)
Input is a linked listMerge sort usually wins; quicksort on lists works only with a 3-list partition
"sort an array" on a judge with a time limit and large Use the library sort, or a randomized 3-way quicksort if you must write one
"nuts and bolts", "match two sets with no internal comparisons"Partition one set with an element of the other, alternately

Interviews probe rows four and five: "find the median" is quickselect, and "the input comes from users" means a deterministic pivot is a denial-of-service bug.

Intuition & first principles

Sorting is hard because every element's final position depends on every other element. Partitioning breaks that dependency. Choose one element, the pivot . After one linear pass, rearrange the array into three parts: elements that belong before , then itself, then elements that belong after . Two facts now hold, and they are the whole algorithm:

  1. is in its final sorted position. Exactly as many elements are smaller-or-equal as there are positions to its left.
  2. No element will ever cross again. The left part and the right part are independent sorting problems.

So sort each part the same way. Merge sort does the easy split (cut at the middle) and the hard combine (merge). Quicksort does the hard split (partition) and has no combine step at all — when both halves are sorted, the whole array is sorted because the halves are already in the right relative order.

One partition is linear work, so the question is how many levels there are. Perfect median pivots give levels ( total); always-smallest pivots give levels (). Almost every pivot sequence is much closer to the first picture. A pivot does not need to be the median to be good. Any pivot that lands in the middle half of the values (between the 25th and 75th percentiles) leaves both sides at most of the size, and that still gives levels. A random element lands in the middle half half the time.

The precise statement, which the Correctness and Complexity sections prove: with a uniformly random pivot, quicksort is always correct and makes comparisons in expectation, where is the -th harmonic number. The worst case, comparisons, has probability so small that it is irrelevant on random data — and only on random data. Whoever controls the pivot choice or the input order controls the running time, which is why the second half of this lesson is about adversaries.

flowchart TD
    A["quicksort(a, lo, hi)"] --> B{"hi - lo + 1 <= 1 ?"}
    B -->|"yes"| R["return: already sorted"]
    B -->|"no"| C["choose pivot p"]
    C --> D["partition: smaller | p | larger"]
    D --> E["quicksort(left part)"]
    D --> F["quicksort(right part)"]
    E --> G["done: no merge step needed"]
    F --> G

Mechanics

Lomuto partition

Lomuto's scheme uses the last element as the pivot and one left-to-right scan. It is the read/write pointer pattern (Family B) from Two Pointers: index j reads every element once; index i marks the end of the "small" region.

pivot = a[hi]
i = lo - 1
for j in lo .. hi-1:
    if a[j] <= pivot:
        i += 1
        swap a[i], a[j]
swap a[i+1], a[hi]          # pivot into its final place
return i + 1

Invariant (Lomuto): at the top of each iteration,

  • a[lo..i] are all pivot,
  • a[i+1..j-1] are all pivot,
  • a[j..hi-1] are not yet examined,
  • a[hi] is the pivot.
flowchart LR
    A["a[lo..i]<br/>all <= pivot"] --> B["a[i+1..j-1]<br/>all > pivot"]
    B --> C["a[j..hi-1]<br/>unexamined"]
    C --> D["a[hi]<br/>pivot"]

When a[j] <= pivot, the swap moves it from the right edge of the "large" region to the right edge of the "small" region, and the first large element moves to position j — the large region simply slides one place right. When a[j] > pivot, extending j grows the large region. Either way the invariant holds for j + 1. At the end, j = hi, the unexamined region is empty, and swapping a[i+1] (the first large element, or the pivot itself if there is none) with a[hi] puts the pivot between the two regions.

Trace of lomuto_partition([7, 2, 1, 8, 6, 3, 5, 4], 0, 7) with pivot 4 (computed by script — the visualizer below replays the same run):

Stepja[j]a[j] ≤ 4?i afterActionArray after
0———−1pivot = a[7] = 4[7, 2, 1, 8, 6, 3, 5, 4]
107no−1skip[7, 2, 1, 8, 6, 3, 5, 4]
212yes0swap a[0], a[1][2, 7, 1, 8, 6, 3, 5, 4]
321yes1swap a[1], a[2][2, 1, 7, 8, 6, 3, 5, 4]
438no1skip[2, 1, 7, 8, 6, 3, 5, 4]
546no1skip[2, 1, 7, 8, 6, 3, 5, 4]
653yes2swap a[2], a[5][2, 1, 3, 8, 6, 7, 5, 4]
765no2skip[2, 1, 3, 8, 6, 7, 5, 4]
8———2swap a[3], a[7] (pivot home)[2, 1, 3, 4, 6, 7, 5, 8]

The function returns 3. Seven comparisons (always for a subarray of ), four swaps. Note what happened to 7: it was swapped from index 0 to 1, then to 2, then to 5 — Lomuto moves "large" elements repeatedly, which is why it does about three times as many swaps as Hoare on random data.

Lomuto keeps a[lo..i] ≤ pivot and a[i+1..j−1] > pivot as j scans; one last swap drops the pivot between the two regions, at its final sorted index.

Hoare partition

Hoare's scheme scans from both ends at once (Family A of Two Pointers). The CLRS form uses a[lo] as the pivot:

pivot = a[lo]
i = lo - 1;  j = hi + 1
loop:
    do i += 1 while a[i] < pivot
    do j -= 1 while a[j] > pivot
    if i >= j: return j
    swap a[i], a[j]

Invariant (Hoare): after every swap, a[lo..i] are all pivot and a[j..hi] are all pivot. The left scan stops at an element that is not smaller than the pivot (a candidate for the right side); the right scan stops at one that is not larger (a candidate for the left side); the swap fixes both at once.

flowchart LR
    A["a[lo..i-1]<br/>all <= pivot"] --> B["a[i..j]<br/>unexamined"]
    B --> C["a[j+1..hi]<br/>all >= pivot"]
    I["i scans right,<br/>stops at >= pivot"] -.-> B
    J["j scans left,<br/>stops at <= pivot"] -.-> B

The return value is different in kind from Lomuto's. Hoare returns a split point j, with every element of a[lo..j] every element of a[j+1..hi]. The pivot is not necessarily at index j, and it is not necessarily in its final position. The recursive calls are therefore sort(lo, j) and sort(j + 1, hi) — including j on the left. Writing sort(lo, j - 1) (Lomuto's habit) silently drops an element from consideration.

Trace of hoare_partition([7, 2, 1, 8, 6, 3, 5, 4], 0, 7) with pivot a[0] = 7 (computed by script):

Roundi stops ata[i]j stops ata[j]i ≥ j?ActionArray after
10774noswap a[0], a[7][4, 2, 1, 8, 6, 3, 5, 7]
23865noswap a[3], a[6][4, 2, 1, 5, 6, 3, 8, 7]
36853yesreturn 5[4, 2, 1, 5, 6, 3, 8, 7]

Split point 5: a[0..5] = [4, 2, 1, 5, 6, 3] are all , a[6..7] = [8, 7] are all . Two swaps instead of Lomuto's four on the same array, and the pivot 7 ended at index 7, not at the split point. Element a[5] = 3 is not the pivot — the proof that you must recurse on [lo, j], not [lo, j-1].

The Hoare off-by-one traps

Hoare's partition is short and fragile. These are the mistakes that make it loop forever, read out of bounds or sort incorrectly, each one verified on a small input.

  1. Pivot at a[hi] with recursion on [lo, j] and [j+1, hi]. On [1, 2], pivot 2: i stops at index 1 (2 is not < 2), j stops at index 1 (2 is not > 2), i >= j, return 1. The left call is sort(0, 1) — the same range — forever. The rule: with the [lo, j] / [j+1, hi] split, the pivot must not be the maximum-index element; use a[lo] or the lower middle a[lo + (hi - lo) // 2]. With the upper middle (lo + hi + 1) // 2 the same infinite loop appears on [1, 2].
  2. <= and >= in the scans. Writing while a[i] <= pivot lets i run off the end of the array when the pivot is the maximum, because nothing stops it. It also destroys the balanced split on equal keys (next point). The scans must be strict, so that both stop on elements equal to the pivot.
  3. Recursing on [lo, j-1] and [j+1, hi]. Shown above: index j holds an arbitrary element of the left side, not the pivot.
  4. while instead of do … while. The scans must move before the first test, otherwise after a swap of two elements equal to the pivot neither index moves and the loop spins.
  5. mid = (lo + hi) / 2 overflow. In Java and C++ with 32-bit indices and arrays above elements, lo + hi overflows. Write lo + (hi - lo) / 2. (The same bug lived in Java's binary search for nine years; see Binary Search Mastery.)

Why stop on equal keys, which causes seemingly pointless swaps? On equal values, strict scans stop at every element, swap, and meet in the middle: a perfect split. We measured 25,726 comparisons to sort 2,000 equal values this way. Lomuto, by contrast, puts every equal element on the left (a[j] <= pivot is always true), returns hi, and recurses on elements: exactly comparisons for the same array. Sedgewick calls the equal-key behaviour the single most important practical difference between partition schemes.

Three-way partition (Dijkstra, Bentley–McIlroy)

Hoare's scheme survives duplicates but still re-sorts them: a run of 1,000 copies of the pivot value gets split and recursed into. Three-way partitioning gathers all keys equal to the pivot in the middle and never touches them again. Dijkstra's version is the Dutch national flag algorithm with the pivot playing the role of "white":

p = a[lo];  lt = lo;  i = lo + 1;  gt = hi
while i <= gt:
    if a[i] < p:  swap a[lt], a[i];  lt += 1;  i += 1
    elif a[i] > p: swap a[i], a[gt];  gt -= 1        # i stays: new a[i] unexamined
    else:          i += 1
# a[lo..lt-1] < p,  a[lt..gt] == p,  a[gt+1..hi] > p

On [3, 1, 3, 5, 3, 2, 3, 4] with pivot 3 it returns (lt, gt) = (2, 5) and leaves [1, 2, 3, 3, 3, 3, 4, 5]; the recursion continues only on [1, 2] and [4, 5]. With distinct keys, three-way quicksort does work rather than ; an array of copies of one value is sorted in a single linear pass.

Dijkstra's loop does more swaps than Hoare's on arrays with few duplicates (every element greater than the pivot is swapped). Bentley and McIlroy's 1993 scheme fixes that: it runs a Hoare-style two-ended scan, but when either scan meets a key equal to the pivot it swaps it to the far end of the array (left equals to the extreme left, right equals to the extreme right). When the scans cross, the two blocks of equal keys are swapped into the middle. It costs almost nothing when keys are distinct and is what their qsort (and later many C libraries) shipped. Sedgewick and Bentley later showed that three-way quicksort is entropy-optimal within a constant factor: its comparison count is proportional to , where is the Shannon entropy of the key frequencies.

Pivot choice

The pivot rule decides which inputs are slow.

RuleCost per partitionBad inputsNotes
First or last element0Sorted, reverse-sorted, all-equal (Lomuto)Quadratic on the most common real-world input: already sorted data
Middle element0Constructed "organ-pipe" and other patternsFine on sorted input; still deterministic, so attackable
Uniformly random element1 RNG callNone in expectationExpected compares on every input
Median of 3 (first, middle, last)2–3 comparesMusser's median-of-3 killer, McIlroy adversaryCuts expected compares to about ; protects sorted input
Ninther (median of three medians of 3)8–12 comparesAdversary onlyBentley–McIlroy use it for ; better pivot estimate on big arrays
True median (median of medians)NoneWorst case but slower in practice than introsort

Median of 3 samples a[lo], a[mid] and a[hi] and uses the middle value. On sorted input that is the exact median, so the worst common case becomes the best case. It also reduces the expected comparison count from to (Knuth, TAOCP Vol. 3, §5.2.2; we quote the constant rather than re-derive it). Sorting the three samples in place also leaves a sentinel at each end, so the inner scans need no bounds checks.

The ninther, John Tukey's "pseudomedian of nine", is the median of the medians of three groups of three evenly spaced elements. It estimates the true median better on large arrays; Bentley–McIlroy's qsort uses it for and pdqsort uses it on large ranges.

Random pivots move the randomness from the input to the algorithm. A deterministic quicksort has an average case over inputs, and an adversary picks the bad ones; a randomized quicksort has an expected running time for every input. Shuffling once up front (Sedgewick's recommendation) gives the same guarantee.

The worst case and the adversary

With a first-element pivot, sorting [1, 2, 3, …, n] partitions off one element per level: comparisons and levels of recursion. For that is about comparisons and a 100,000-frame stack that crashes most runtimes before it finishes. Median-of-3 fixes sorted input, but Musser (1997) constructed explicit median-of-3 killer sequences on which it is still quadratic.

McIlroy's 1999 paper, "A Killer Adversary for Quicksort" (Software: Practice and Experience 29(4)), goes further: it breaks any deterministic quicksort without knowing its code, as long as the sort calls a user-supplied comparison function (as C's qsort does). The adversary starts with every element in a state called gas — value unknown. When the sort compares two gas elements, the adversary freezes one of them to the next smallest available value, preferring to freeze the one it does not believe is the current pivot candidate. A frozen value never changes, so the answers stay consistent, and at the end the frozen values are a concrete input array. Because the sort is deterministic, replaying that array with ordinary comparisons repeats the identical sequence of comparisons — quadratic. We implemented it against a median-of-3 quicksort (see Variations): at it forced 4,023,984 comparisons, against 63,311 on a random permutation, a factor of 64, and almost exactly .

This is an algorithmic complexity attack, the same class of denial-of-service as hash flooding in Hash Tables (Crosby and Wallach, USENIX Security 2003). Two defences work: randomize unpredictably, or bound the worst case (introsort, below).

Recursion depth and tail-recursing on the smaller side

Quicksort's time and its stack are different problems. Even with random pivots, a naive implementation that recurses on both sides has a worst-case recursion depth of . The fix is one of the best tricks in the lesson: recurse into the smaller side, loop on the larger side.

while hi - lo >= 1:
    p = partition(a, lo, hi)
    if (p - lo) < (hi - p):
        sort(lo, p - 1);  lo = p + 1      # recurse small, iterate large
    else:
        sort(p + 1, hi);  hi = p - 1

Every recursive call is on a subarray at most half the size of its caller's, so after nested calls the subarray has at most elements and the depth is at most — about 30 frames for a billion elements, regardless of pivot quality. The while loop is what tail-call optimisation would have made of the second call. It fixes space, not time: bad pivots still cost comparisons.

Introsort

Introsort (Musser, 1997, "Introspective Sorting and Selection Algorithms", Software: Practice and Experience 27(8)) makes the worst case while keeping quicksort's speed on normal inputs. It runs median-of-3 quicksort with a depth budget of . Each partition spends one unit. If a subarray is reached with the budget exhausted, the pivots have been bad far more often than chance predicts, so introsort sorts that subarray with heapsort, which is worst case and in place. Small subarrays (16 elements in libstdc++) are left for a final insertion sort, which beats quicksort's overhead at that size.

flowchart TD
    S["introsort(a): depth = 2 * floor(log2 n)"] --> Q{"size > 16 ?"}
    Q -->|"no"| INS["insertion sort the range"]
    Q -->|"yes"| D{"depth == 0 ?"}
    D -->|"yes: pivots keep failing"| HS["heapsort the range: O(m log m) guaranteed"]
    D -->|"no"| P["depth -= 1, median-of-3 pivot, Hoare partition"]
    P --> SM["recurse on the smaller side"]
    P --> LG["loop on the larger side"]
    SM --> Q
    LG --> Q

Why does the total stay ? Quicksort work above the depth cutoff is at most per level for levels: . The subarrays handed to heapsort are disjoint, so their sizes sum to at most and the heapsort work is . Insertion sort runs on disjoint ranges of at most 16 elements: . On random data the depth limit is essentially never hit, so introsort runs at quicksort speed. That is not automatic: with a single random pivot the deepest recursion path is about (the height of a random binary search tree, Devroye 1986), which exceeds the budget — we measured maximum depths of 37–41 at against a budget of 32. Two details save introsort: median-of-3 pivots are much better balanced, and subarrays of 16 or fewer elements do not spend budget. Our introsort recorded zero heapsort fallbacks over 25 random arrays of and doubles. Against McIlroy's adversary it degrades gracefully to heapsort speed instead of to .

libstdc++'s std::sort is exactly this design: __introsort_loop with a depth limit of 2 * __lg(n), median-of-3 pivot selection, an unguarded Hoare-style partition, a _S_threshold of 16, and a final insertion sort over the whole array. Microsoft's STL is also an introsort. libc++ historically used a different quicksort and later added an introsort-style depth limit (we have not pinned down the release, so check your version's source).

The ladder: brute force → better → optimal

Rung 0 — sort by brute force. Try permutations until one is sorted: . Useless except as a test oracle for , and as a reminder that the information-theoretic minimum is comparisons (proved in Non-Comparison Sorts).

Rung 1 — elementary sorts. Insertion sort is worst case, on sorted input, and the fastest method for . See Elementary Sorts. It improves by not re-examining work: each element is inserted into an already-sorted prefix.

Rung 2 — textbook quicksort (Lomuto, last-element pivot). Expected on random input, but on sorted input, reverse-sorted input and arrays with many equal keys, with stack. It improves on rung 1 because each partition settles one element and splits the rest into independent halves.

Rung 3 — randomized Hoare quicksort with smaller-side recursion. Expected comparisons on every input, about a third of Lomuto's swaps, balanced splits on equal keys, and stack guaranteed. Still worst case with vanishing probability, and attackable if the random generator is predictable.

Rung 4 — three-way quicksort. Adds for distinct keys; linear on all-equal input. Costs extra swaps on distinct keys unless you use Bentley–McIlroy.

Rung 5 — introsort. Median-of-3 (or ninther) pivots, Hoare partition, smaller-side recursion, insertion sort below 16 elements, heapsort when the depth budget runs out. worst case, quicksort speed on normal data, stack. This is "optimal" in the engineering sense for an unstable in-place comparison sort; pdqsort (rung 6, in Sorting in the Real World) adds pattern detection and branchless partitioning on top.

RungTime (expected)Time (worst)Extra spaceEqual keysAdversary-safe
Permutation brute force——
Insertion sortfineyes, but slow
Lomuto, last pivot on random (sorted, equal) stackquadraticno
Random Hoare, small-side recursion compares, negligible probabilitybalancedyes, if RNG is unpredictable
Random 3-way, negligible probabilitylinearas above
Introsort compares (median-of-3)balancedyes

Correctness

Lomuto partition is correct

Claim. lomuto_partition(a, lo, hi) returns with a[lo..p-1] a[p] a[p+1..hi], and the multiset of elements is unchanged.

Proof. Only swaps modify the array, so the multiset is preserved. We show the invariant stated in Mechanics holds at the top of every iteration.

  • Initialisation (j = lo, i = lo - 1): a[lo..i] and a[i+1..j-1] are empty; a[hi] is the pivot.
  • Maintenance. If a[j] > pivot, incrementing j appends a[j] to the "> pivot" region; nothing else changes. If a[j] <= pivot, i is incremented and a[i] and a[j] are swapped. Before the swap, a[i] (new i) was the first element of the "> pivot" region, or i == j if that region was empty. After the swap a[i] <= pivot extends the small region, and the large element moves to index j, the new right end of the large region. Both regions keep their properties when j increments.
  • Termination. The loop ends with j = hi: a[lo..i] pivot and a[i+1..hi-1] pivot. Swapping a[i+1] with a[hi] places the pivot at p = i + 1 and moves a large element (if any) to hi, which is still in the large region. ∎

Hoare partition is correct and stays in bounds

Claim. With pivot a[lo] and lo < hi, hoare_partition terminates without indexing outside [lo, hi], and returns j with such that every element of a[lo..j] is every element of a[j+1..hi].

Proof sketch (CLRS Problem 7-1 asks for the full version).

  • First round. i stops at lo, because a[lo] is the pivot and is not smaller than itself. j stops at some index for the same reason. If j == lo the function returns lo . Otherwise i < j and they swap.
  • Sentinels. After any swap, a[i] <= pivot and a[j] >= pivot. In the next round the left scan cannot pass the old j (that element is pivot, which stops it) and the right scan cannot pass the old i. So no scan leaves [lo, hi].
  • Invariant. After each swap, a[lo..i] pivot and a[j..hi] pivot: the scans only skip elements on the correct side, and the swap puts a element at i and a element at j.
  • Return. When i >= j, everything the left scan passed over in the final round was pivot, so (with the invariant) all of a[lo..i-1] are pivot; likewise all of a[j+1..hi] are pivot. Since , every index in [lo, j] is either below i, or equal to i (when ). In the second case a[j] stopped the right scan, so it is pivot as well. Hence every element of a[lo..j] is pivot every element of a[j+1..hi].
  • . If the first round already stops with j == hi, then i == lo < hi and they swap, after which j decreases at least once more. So the returned j is at most hi - 1. Both sides are non-empty and strictly smaller than the input, which is what makes the recursion terminate. ∎

That last point is exactly what breaks with a pivot at a[hi]: the symmetric argument gives instead, so the left side can be the whole array.

Quicksort is correct

Claim. quicksort(a, lo, hi) sorts a[lo..hi].

Proof by strong induction on . For the range is trivially sorted. For , partition returns a split with every element of the left part every element of the right part, and both parts have fewer than elements (for Lomuto because the pivot is excluded, for Hoare by the property). By the induction hypothesis the recursive calls sort each part. A sorted left part, followed by (for Lomuto) the pivot, followed by a sorted right part, with all left all right, is sorted. The smaller-side loop is the same recursion with the second call replaced by updating lo/hi, so the argument is unchanged. ∎

The three-way version is identical with three parts, the middle one already sorted because its elements are equal. Introsort is correct because each of its branches — insertion sort, heapsort, or partition-and-recurse — sorts its range, and the partition-and-recurse branch is the quicksort argument above.

Complexity

Expected comparisons with a random pivot: the indicator-variable proof

Let the elements in sorted order be (assume distinct keys). Count comparisons in the model where a partition of elements compares the pivot with each of the other (exactly what Lomuto does). Two elements are compared at most once, because every comparison involves the current pivot, and a pivot is excluded from all later recursive calls. So the total number of comparisons is

When are and compared? Look at the set of elements. As long as no pivot has been chosen from , all of stays in the same subarray (a pivot outside the range puts the whole range on one side). The first pivot chosen from decides everything. If it is or , the two are compared during that partition. If it is anything strictly between them, they are separated into different subarrays and never meet. With a uniformly random pivot, each element of is equally likely to be first, so

By linearity of expectation (which needs no independence),

Doing the sum exactly gives . Since with ,

The constant is where "quicksort makes about 39% more comparisons than the lower bound " comes from. We checked the closed form against the recurrence (they agree to floating-point precision at ) and tabulated it:

nExact Ratio to
1024460.74
1,00010,98613,8161.10
100,0002,018,0532,302,5841.22
1,000,00024,785,48227,631,0141.24

The linear correction is large: even at a million elements the ratio is 1.24, not 1.39. Quote as the asymptotic constant, not as a prediction for your benchmark.

Swaps: why Hoare beats Lomuto

Comparisons are not the only cost. In a simulation on random permutations of distinct keys (three runs, random pivots, our code), Lomuto made about swaps (1.06 million), and Hoare about swaps (0.39 million) — a factor of 2.7. The classical analysis gives exchanges for Hoare-style partitioning (Sedgewick); Lomuto swaps every element smaller than the pivot, about half of each partition. On arrays of large records, where a swap moves many bytes, this matters as much as the comparison count. The table summarises:

SchemeComparisons per partition of Swaps per partition (random)All-equal keys
Lomutoabout quadratic: returns hi every time
Hoareabout (scans overlap by one or two)about balanced split,
Dijkstra 3-wayup to (two compares per element)up to one pass,
Bentley–McIlroy 3-wayabout Hoare'sabout Hoare's plus equal keysone pass,

Best, average, worst

  • Best case: every pivot is the median: , about comparisons. (With three-way partitioning and all-equal keys, .)
  • Expected case (random pivot, any input): , with a sharp concentration: the probability of exceeding a constant multiple of the mean decays faster than any polynomial in (McDiarmid and Hayward, 1996). The recursion depth is with high probability too: about for a typical element and about for the deepest path.
  • Worst case: , exactly comparisons with Lomuto, when every pivot is an extreme. Deterministic pivots hit it on specific inputs; random pivots hit it with probability at most for the fully degenerate sequence.
  • Space: in place, plus the stack. worst case with smaller-side recursion; worst case without it.
  • Stability: none of the in-place partitions is stable. Long-distance swaps reorder equal keys: Hoare-partitioning [(2,a), (1,b), (2,c), (1,d)] by key with pivot key 2 swaps (2,a) with (1,d) and leaves [(1,d), (1,b), (2,c), (2,a)] — both pairs of equal keys now in reverse order (verified by script).

Constants and the cache

Quicksort's speed on real machines comes from its memory pattern. Each partition streams through a contiguous range from one or both ends — the prefetcher's favourite pattern — and once a subarray fits in L1 or L2 cache, all recursion below it runs from cache. LaMarca and Ladner's study of sorting and caches (SODA 1997) found quicksort incurs far fewer cache misses per element than heapsort, whose sift-down jumps between index and and misses on almost every level once the heap exceeds the cache. That is the main reason Heap Sort loses to quicksort in practice despite a better worst case.

The other cost is branch misprediction: with a median pivot, a[j] <= pivot is a coin flip the CPU cannot predict. BlockQuicksort (Edelkamp and Weiß, 2016) and pdqsort replace the branch with branch-free block partitioning. See Data Structures in Memory for the hardware behind both effects.

Implementation

The canonical code: Lomuto, Hoare and Dijkstra three-way partitions, and a randomized quicksort that uses any of them with smaller-side recursion. All four blocks run the same tests: the two traced partitions above, the three-way example, and full sorts of a 2,000-element array with heavy duplication (values generated by the MINSTD generator , seed 42, reduced mod 1000), a sorted array, a reversed array, an all-equal array, an empty array and a singleton, each compared with the built-in sort.

import random


def lomuto_partition(a: list[int], lo: int, hi: int) -> int:
    """Partition a[lo..hi] around pivot a[hi]; return its final index p.
    Afterwards a[lo..p-1] <= a[p] < a[p+1..hi]."""
    pivot = a[hi]
    i = lo - 1                        # a[lo..i] <= pivot
    for j in range(lo, hi):           # a[i+1..j-1] > pivot
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1


def hoare_partition(a: list[int], lo: int, hi: int) -> int:
    """Partition a[lo..hi] around pivot a[lo]; return j with lo <= j < hi and
    every element of a[lo..j] <= every element of a[j+1..hi]."""
    pivot = a[lo]
    i, j = lo - 1, hi + 1
    while True:
        i += 1
        while a[i] < pivot:           # strict: stop on keys equal to the pivot
            i += 1
        j -= 1
        while a[j] > pivot:
            j -= 1
        if i >= j:
            return j
        a[i], a[j] = a[j], a[i]


def partition3(a: list[int], lo: int, hi: int) -> tuple[int, int]:
    """Dijkstra 3-way partition around a[lo]; return (lt, gt) with
    a[lo..lt-1] < p, a[lt..gt] == p, a[gt+1..hi] > p."""
    p = a[lo]
    lt, i, gt = lo, lo + 1, hi
    while i <= gt:
        if a[i] < p:
            a[lt], a[i] = a[i], a[lt]
            lt += 1
            i += 1
        elif a[i] > p:
            a[i], a[gt] = a[gt], a[i]
            gt -= 1                   # i stays: the swapped-in value is unexamined
        else:
            i += 1
    return lt, gt


def quicksort(a: list[int], scheme: str = "hoare", rng: random.Random | None = None) -> list[int]:
    """Randomized in-place quicksort. Recurses on the smaller side and loops on
    the larger, so the stack depth is at most log2(n) whatever the pivots."""
    rng = rng or random.Random(0)

    def sort(lo: int, hi: int) -> None:
        while lo < hi:
            r = rng.randint(lo, hi)
            if scheme == "lomuto":
                a[r], a[hi] = a[hi], a[r]
                p = lomuto_partition(a, lo, hi)
                left, right = (lo, p - 1), (p + 1, hi)
            elif scheme == "hoare":
                a[r], a[lo] = a[lo], a[r]
                p = hoare_partition(a, lo, hi)
                left, right = (lo, p), (p + 1, hi)       # j belongs to the left side
            else:                                         # "3way"
                a[r], a[lo] = a[lo], a[r]
                lt, gt = partition3(a, lo, hi)
                left, right = (lo, lt - 1), (gt + 1, hi)
            if left[1] - left[0] < right[1] - right[0]:
                sort(*left)
                lo, hi = right
            else:
                sort(*right)
                lo, hi = left

    sort(0, len(a) - 1)
    return a


def minstd(seed: int, n: int, mod: int) -> list[int]:
    out, x = [], seed
    for _ in range(n):
        x = x * 48271 % 2147483647
        out.append(x % mod)
    return out


if __name__ == "__main__":
    a = [7, 2, 1, 8, 6, 3, 5, 4]
    assert lomuto_partition(a, 0, 7) == 3 and a == [2, 1, 3, 4, 6, 7, 5, 8]
    a = [7, 2, 1, 8, 6, 3, 5, 4]
    assert hoare_partition(a, 0, 7) == 5 and a == [4, 2, 1, 5, 6, 3, 8, 7]
    a = [3, 1, 3, 5, 3, 2, 3, 4]
    assert partition3(a, 0, 7) == (2, 5) and a == [1, 2, 3, 3, 3, 3, 4, 5]
    cases = [minstd(42, 2000, 1000), list(range(2000)), list(range(2000, 0, -1)), [7] * 2000, [], [1]]
    for scheme in ("lomuto", "hoare", "3way"):
        for c in cases:
            assert quicksort(list(c), scheme) == sorted(c), scheme
    print("ok")
import java.util.Arrays;
import java.util.Random;

public class QuickSortSchemes {
    static void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }

    /** Pivot a[hi]; returns p with a[lo..p-1] <= a[p] < a[p+1..hi]. */
    static int lomutoPartition(int[] a, int lo, int hi) {
        int pivot = a[hi];
        int i = lo - 1;
        for (int j = lo; j < hi; j++) {
            if (a[j] <= pivot) {
                i++;
                swap(a, i, j);
            }
        }
        swap(a, i + 1, hi);
        return i + 1;
    }

    /** Pivot a[lo]; returns j in [lo, hi) with a[lo..j] <= a[j+1..hi]. */
    static int hoarePartition(int[] a, int lo, int hi) {
        int pivot = a[lo];
        int i = lo - 1, j = hi + 1;
        while (true) {
            do { i++; } while (a[i] < pivot);
            do { j--; } while (a[j] > pivot);
            if (i >= j) return j;
            swap(a, i, j);
        }
    }

    /** Dijkstra 3-way around a[lo]; returns {lt, gt}. */
    static int[] partition3(int[] a, int lo, int hi) {
        int p = a[lo], lt = lo, i = lo + 1, gt = hi;
        while (i <= gt) {
            if (a[i] < p) swap(a, lt++, i++);
            else if (a[i] > p) swap(a, i, gt--);
            else i++;
        }
        return new int[] {lt, gt};
    }

    static int[] quicksort(int[] a, String scheme, Random rng) {
        sort(a, 0, a.length - 1, scheme, rng);
        return a;
    }

    private static void sort(int[] a, int lo, int hi, String scheme, Random rng) {
        while (lo < hi) {
            int r = lo + rng.nextInt(hi - lo + 1);
            int l1, r1, l2, r2;
            if (scheme.equals("lomuto")) {
                swap(a, r, hi);
                int p = lomutoPartition(a, lo, hi);
                l1 = lo; r1 = p - 1; l2 = p + 1; r2 = hi;
            } else if (scheme.equals("hoare")) {
                swap(a, r, lo);
                int p = hoarePartition(a, lo, hi);
                l1 = lo; r1 = p; l2 = p + 1; r2 = hi;
            } else {
                swap(a, r, lo);
                int[] lg = partition3(a, lo, hi);
                l1 = lo; r1 = lg[0] - 1; l2 = lg[1] + 1; r2 = hi;
            }
            if (r1 - l1 < r2 - l2) { sort(a, l1, r1, scheme, rng); lo = l2; hi = r2; }
            else { sort(a, l2, r2, scheme, rng); lo = l1; hi = r1; }
        }
    }

    static int[] minstd(long seed, int n, int mod) {
        int[] out = new int[n];
        long x = seed;
        for (int k = 0; k < n; k++) {
            x = x * 48271 % 2147483647L;
            out[k] = (int) (x % mod);
        }
        return out;
    }

    static void check(boolean ok, String msg) {
        if (!ok) throw new AssertionError(msg);
    }

    public static void main(String[] args) {
        int[] a = {7, 2, 1, 8, 6, 3, 5, 4};
        check(lomutoPartition(a, 0, 7) == 3 && Arrays.equals(a, new int[] {2, 1, 3, 4, 6, 7, 5, 8}), "lomuto");
        a = new int[] {7, 2, 1, 8, 6, 3, 5, 4};
        check(hoarePartition(a, 0, 7) == 5 && Arrays.equals(a, new int[] {4, 2, 1, 5, 6, 3, 8, 7}), "hoare");
        a = new int[] {3, 1, 3, 5, 3, 2, 3, 4};
        int[] lg = partition3(a, 0, 7);
        check(lg[0] == 2 && lg[1] == 5 && Arrays.equals(a, new int[] {1, 2, 3, 3, 3, 3, 4, 5}), "3way");

        int n = 2000;
        int[] sorted = new int[n], reversed = new int[n], equal = new int[n];
        for (int k = 0; k < n; k++) { sorted[k] = k; reversed[k] = n - k; equal[k] = 7; }
        int[][] cases = {minstd(42, n, 1000), sorted, reversed, equal, {}, {1}};
        for (String scheme : new String[] {"lomuto", "hoare", "3way"}) {
            for (int[] c : cases) {
                int[] expect = c.clone();
                Arrays.sort(expect);
                check(Arrays.equals(quicksort(c.clone(), scheme, new Random(0)), expect), scheme);
            }
        }
        System.out.println("ok");
    }
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <random>
#include <string>
#include <utility>
#include <vector>

// Pivot a[hi]; returns p with a[lo..p-1] <= a[p] < a[p+1..hi].
int lomutoPartition(std::vector<int>& a, int lo, int hi) {
    int pivot = a[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; ++j) {
        if (a[j] <= pivot) std::swap(a[++i], a[j]);
    }
    std::swap(a[i + 1], a[hi]);
    return i + 1;
}

// Pivot a[lo]; returns j in [lo, hi) with a[lo..j] <= a[j+1..hi].
int hoarePartition(std::vector<int>& a, int lo, int hi) {
    int pivot = a[lo];
    int i = lo - 1, j = hi + 1;
    while (true) {
        do { ++i; } while (a[i] < pivot);
        do { --j; } while (a[j] > pivot);
        if (i >= j) return j;
        std::swap(a[i], a[j]);
    }
}

// Dijkstra 3-way around a[lo]; returns {lt, gt}.
std::pair<int, int> partition3(std::vector<int>& a, int lo, int hi) {
    int p = a[lo], lt = lo, i = lo + 1, gt = hi;
    while (i <= gt) {
        if (a[i] < p) std::swap(a[lt++], a[i++]);
        else if (a[i] > p) std::swap(a[i], a[gt--]);
        else ++i;
    }
    return {lt, gt};
}

void sortRange(std::vector<int>& a, int lo, int hi, const std::string& scheme, std::mt19937& rng) {
    while (lo < hi) {
        int r = std::uniform_int_distribution<int>(lo, hi)(rng);
        int l1, r1, l2, r2;
        if (scheme == "lomuto") {
            std::swap(a[r], a[hi]);
            int p = lomutoPartition(a, lo, hi);
            l1 = lo; r1 = p - 1; l2 = p + 1; r2 = hi;
        } else if (scheme == "hoare") {
            std::swap(a[r], a[lo]);
            int p = hoarePartition(a, lo, hi);
            l1 = lo; r1 = p; l2 = p + 1; r2 = hi;
        } else {
            std::swap(a[r], a[lo]);
            auto [lt, gt] = partition3(a, lo, hi);
            l1 = lo; r1 = lt - 1; l2 = gt + 1; r2 = hi;
        }
        if (r1 - l1 < r2 - l2) { sortRange(a, l1, r1, scheme, rng); lo = l2; hi = r2; }
        else { sortRange(a, l2, r2, scheme, rng); lo = l1; hi = r1; }
    }
}

std::vector<int> quicksort(std::vector<int> a, const std::string& scheme) {
    std::mt19937 rng(0);
    sortRange(a, 0, static_cast<int>(a.size()) - 1, scheme, rng);
    return a;
}

std::vector<int> minstd(std::uint64_t seed, int n, int mod) {
    std::vector<int> out;
    std::uint64_t x = seed;
    for (int k = 0; k < n; ++k) {
        x = x * 48271 % 2147483647ULL;
        out.push_back(static_cast<int>(x % mod));
    }
    return out;
}

int main() {
    std::vector<int> a{7, 2, 1, 8, 6, 3, 5, 4};
    assert(lomutoPartition(a, 0, 7) == 3 && (a == std::vector<int>{2, 1, 3, 4, 6, 7, 5, 8}));
    a = {7, 2, 1, 8, 6, 3, 5, 4};
    assert(hoarePartition(a, 0, 7) == 5 && (a == std::vector<int>{4, 2, 1, 5, 6, 3, 8, 7}));
    a = {3, 1, 3, 5, 3, 2, 3, 4};
    assert((partition3(a, 0, 7) == std::pair<int, int>{2, 5}) && (a == std::vector<int>{1, 2, 3, 3, 3, 3, 4, 5}));

    const int n = 2000;
    std::vector<int> sorted(n), reversed(n), equal(n, 7);
    for (int k = 0; k < n; ++k) { sorted[k] = k; reversed[k] = n - k; }
    std::vector<std::vector<int>> cases{minstd(42, n, 1000), sorted, reversed, equal, {}, {1}};
    for (std::string scheme : {"lomuto", "hoare", "3way"}) {
        for (const auto& c : cases) {
            auto expect = c;
            std::sort(expect.begin(), expect.end());
            assert(quicksort(c, scheme) == expect);
        }
    }
    std::cout << "ok\n";
}
function swap(a: number[], i: number, j: number): void {
  const t = a[i]; a[i] = a[j]; a[j] = t;
}

/** Pivot a[hi]; returns p with a[lo..p-1] <= a[p] < a[p+1..hi]. */
function lomutoPartition(a: number[], lo: number, hi: number): number {
  const pivot = a[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (a[j] <= pivot) swap(a, ++i, j);
  }
  swap(a, i + 1, hi);
  return i + 1;
}

/** Pivot a[lo]; returns j in [lo, hi) with a[lo..j] <= a[j+1..hi]. */
function hoarePartition(a: number[], lo: number, hi: number): number {
  const pivot = a[lo];
  let i = lo - 1, j = hi + 1;
  while (true) {
    do { i++; } while (a[i] < pivot);
    do { j--; } while (a[j] > pivot);
    if (i >= j) return j;
    swap(a, i, j);
  }
}

/** Dijkstra 3-way around a[lo]; returns [lt, gt]. */
function partition3(a: number[], lo: number, hi: number): [number, number] {
  const p = a[lo];
  let lt = lo, i = lo + 1, gt = hi;
  while (i <= gt) {
    if (a[i] < p) swap(a, lt++, i++);
    else if (a[i] > p) swap(a, i, gt--);
    else i++;
  }
  return [lt, gt];
}

type Scheme = "lomuto" | "hoare" | "3way";

function quicksort(a: number[], scheme: Scheme = "hoare"): number[] {
  const sort = (lo: number, hi: number): void => {
    while (lo < hi) {
      const r = lo + Math.floor(Math.random() * (hi - lo + 1));
      let l1: number, r1: number, l2: number, r2: number;
      if (scheme === "lomuto") {
        swap(a, r, hi);
        const p = lomutoPartition(a, lo, hi);
        [l1, r1, l2, r2] = [lo, p - 1, p + 1, hi];
      } else if (scheme === "hoare") {
        swap(a, r, lo);
        const p = hoarePartition(a, lo, hi);
        [l1, r1, l2, r2] = [lo, p, p + 1, hi];
      } else {
        swap(a, r, lo);
        const [lt, gt] = partition3(a, lo, hi);
        [l1, r1, l2, r2] = [lo, lt - 1, gt + 1, hi];
      }
      if (r1 - l1 < r2 - l2) { sort(l1, r1); lo = l2; hi = r2; }
      else { sort(l2, r2); lo = l1; hi = r1; }
    }
  };
  sort(0, a.length - 1);
  return a;
}

function minstd(seed: number, n: number, mod: number): number[] {
  const out: number[] = [];
  let x = seed;
  for (let k = 0; k < n; k++) {
    x = (x * 48271) % 2147483647;   // < 2^53, exact in a double
    out.push(x % mod);
  }
  return out;
}

function check(ok: boolean, msg: string): void {
  if (!ok) throw new Error("check failed: " + msg);
}
const same = (x: number[], y: number[]) => x.length === y.length && x.every((v, k) => v === y[k]);

let a = [7, 2, 1, 8, 6, 3, 5, 4];
check(lomutoPartition(a, 0, 7) === 3 && same(a, [2, 1, 3, 4, 6, 7, 5, 8]), "lomuto");
a = [7, 2, 1, 8, 6, 3, 5, 4];
check(hoarePartition(a, 0, 7) === 5 && same(a, [4, 2, 1, 5, 6, 3, 8, 7]), "hoare");
a = [3, 1, 3, 5, 3, 2, 3, 4];
check(same(partition3(a, 0, 7), [2, 5]) && same(a, [1, 2, 3, 3, 3, 3, 4, 5]), "3way");

const n = 2000;
const sortedArr = Array.from({ length: n }, (_, k) => k);
const reversedArr = Array.from({ length: n }, (_, k) => n - k);
const cases: number[][] = [minstd(42, n, 1000), sortedArr, reversedArr, new Array(n).fill(7), [], [1]];
for (const scheme of ["lomuto", "hoare", "3way"] as Scheme[]) {
  for (const c of cases) {
    const expect = [...c].sort((x, y) => x - y);
    check(same(quicksort([...c], scheme), expect), scheme);
  }
}
console.log("ok");

Production shape: introsort

Median-of-3 pivot moved to a[lo], Hoare partition, smaller-side recursion, insertion sort below 17 elements, heapsort when the depth budget is exhausted. The function returns how many times it fell back to heapsort, so the tests can check that sorted and all-equal inputs never trigger the fallback and that a zero budget forces it.

THRESHOLD = 16


def insertion_sort(a: list[int], lo: int, hi: int) -> None:
    for i in range(lo + 1, hi + 1):
        x, j = a[i], i - 1
        while j >= lo and a[j] > x:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x


def heapsort_range(a: list[int], lo: int, hi: int) -> None:
    n = hi - lo + 1

    def sift(i: int, size: int) -> None:
        while True:
            c = 2 * i + 1
            if c >= size:
                return
            if c + 1 < size and a[lo + c] < a[lo + c + 1]:
                c += 1
            if a[lo + i] >= a[lo + c]:
                return
            a[lo + i], a[lo + c] = a[lo + c], a[lo + i]
            i = c

    for i in range(n // 2 - 1, -1, -1):
        sift(i, n)
    for end in range(n - 1, 0, -1):
        a[lo], a[lo + end] = a[lo + end], a[lo]
        sift(0, end)


def median_of_three_to_lo(a: list[int], lo: int, hi: int) -> None:
    mid = lo + (hi - lo) // 2
    if a[mid] < a[lo]:
        a[mid], a[lo] = a[lo], a[mid]
    if a[hi] < a[lo]:
        a[hi], a[lo] = a[lo], a[hi]
    if a[hi] < a[mid]:
        a[hi], a[mid] = a[mid], a[hi]
    a[lo], a[mid] = a[mid], a[lo]       # median to a[lo]; min now at mid, max at hi


def hoare_partition(a: list[int], lo: int, hi: int) -> int:
    pivot = a[lo]
    i, j = lo - 1, hi + 1
    while True:
        i += 1
        while a[i] < pivot:
            i += 1
        j -= 1
        while a[j] > pivot:
            j -= 1
        if i >= j:
            return j
        a[i], a[j] = a[j], a[i]


def introsort(a: list[int], depth_limit: int | None = None) -> int:
    """Sort a in place; return the number of heapsort fallbacks."""
    n = len(a)
    if depth_limit is None:
        depth_limit = 2 * (n.bit_length() - 1) if n else 0     # 2 * floor(log2 n)
    fallbacks = 0

    def sort(lo: int, hi: int, depth: int) -> None:
        nonlocal fallbacks
        while hi - lo + 1 > THRESHOLD:
            if depth == 0:
                fallbacks += 1
                heapsort_range(a, lo, hi)
                return
            depth -= 1
            median_of_three_to_lo(a, lo, hi)
            p = hoare_partition(a, lo, hi)
            if p - lo < hi - p:
                sort(lo, p, depth)
                lo = p + 1
            else:
                sort(p + 1, hi, depth)
                hi = p
        insertion_sort(a, lo, hi)

    sort(0, n - 1, depth_limit)
    return fallbacks


def minstd(seed: int, n: int, mod: int) -> list[int]:
    out, x = [], seed
    for _ in range(n):
        x = x * 48271 % 2147483647
        out.append(x % mod)
    return out


if __name__ == "__main__":
    n = 2000
    rnd, srt, rev, eq = minstd(42, n, 1000), list(range(n)), list(range(n, 0, -1)), [7] * n
    for c in (rnd, srt, rev, eq, [], [1], [2, 1]):
        b = list(c)
        introsort(b)
        assert b == sorted(c)
    b = list(srt); assert introsort(b) == 0          # median-of-3 splits sorted input perfectly
    b = list(eq); assert introsort(b) == 0           # Hoare splits equal keys in the middle
    b = list(rnd); assert introsort(b, depth_limit=0) == 1 and b == sorted(rnd)   # forced heapsort
    print("ok")
import java.util.Arrays;

public class Introsort {
    static final int THRESHOLD = 16;
    static int fallbacks;

    static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

    static void insertionSort(int[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++) {
            int x = a[i], j = i - 1;
            while (j >= lo && a[j] > x) { a[j + 1] = a[j]; j--; }
            a[j + 1] = x;
        }
    }

    static void sift(int[] a, int lo, int i, int size) {
        while (true) {
            int c = 2 * i + 1;
            if (c >= size) return;
            if (c + 1 < size && a[lo + c] < a[lo + c + 1]) c++;
            if (a[lo + i] >= a[lo + c]) return;
            swap(a, lo + i, lo + c);
            i = c;
        }
    }

    static void heapsortRange(int[] a, int lo, int hi) {
        int n = hi - lo + 1;
        for (int i = n / 2 - 1; i >= 0; i--) sift(a, lo, i, n);
        for (int end = n - 1; end > 0; end--) { swap(a, lo, lo + end); sift(a, lo, 0, end); }
    }

    static void medianOfThreeToLo(int[] a, int lo, int hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < a[lo]) swap(a, mid, lo);
        if (a[hi] < a[lo]) swap(a, hi, lo);
        if (a[hi] < a[mid]) swap(a, hi, mid);
        swap(a, lo, mid);
    }

    static int hoarePartition(int[] a, int lo, int hi) {
        int pivot = a[lo], i = lo - 1, j = hi + 1;
        while (true) {
            do { i++; } while (a[i] < pivot);
            do { j--; } while (a[j] > pivot);
            if (i >= j) return j;
            swap(a, i, j);
        }
    }

    static void sort(int[] a, int lo, int hi, int depth) {
        while (hi - lo + 1 > THRESHOLD) {
            if (depth == 0) { fallbacks++; heapsortRange(a, lo, hi); return; }
            depth--;
            medianOfThreeToLo(a, lo, hi);
            int p = hoarePartition(a, lo, hi);
            if (p - lo < hi - p) { sort(a, lo, p, depth); lo = p + 1; }
            else { sort(a, p + 1, hi, depth); hi = p; }
        }
        insertionSort(a, lo, hi);
    }

    /** Sorts a in place; returns the number of heapsort fallbacks. */
    static int introsort(int[] a, int depthLimit) {
        fallbacks = 0;
        sort(a, 0, a.length - 1, depthLimit);
        return fallbacks;
    }

    static int introsort(int[] a) {
        int depth = a.length == 0 ? 0 : 2 * (31 - Integer.numberOfLeadingZeros(a.length));
        return introsort(a, depth);
    }

    static int[] minstd(long seed, int n, int mod) {
        int[] out = new int[n];
        long x = seed;
        for (int k = 0; k < n; k++) { x = x * 48271 % 2147483647L; out[k] = (int) (x % mod); }
        return out;
    }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    public static void main(String[] args) {
        int n = 2000;
        int[] rnd = minstd(42, n, 1000), srt = new int[n], rev = new int[n], eq = new int[n];
        for (int k = 0; k < n; k++) { srt[k] = k; rev[k] = n - k; eq[k] = 7; }
        for (int[] c : new int[][] {rnd, srt, rev, eq, {}, {1}, {2, 1}}) {
            int[] b = c.clone(), expect = c.clone();
            Arrays.sort(expect);
            introsort(b);
            check(Arrays.equals(b, expect), "sorted");
        }
        check(introsort(srt.clone()) == 0, "sorted input: no fallback");
        check(introsort(eq.clone()) == 0, "equal input: no fallback");
        int[] b = rnd.clone(), expect = rnd.clone();
        Arrays.sort(expect);
        check(introsort(b, 0) == 1 && Arrays.equals(b, expect), "forced heapsort");
        System.out.println("ok");
    }
}
#include <algorithm>
#include <bit>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>

constexpr int THRESHOLD = 16;

void insertionSort(std::vector<int>& a, int lo, int hi) {
    for (int i = lo + 1; i <= hi; ++i) {
        int x = a[i], j = i - 1;
        while (j >= lo && a[j] > x) { a[j + 1] = a[j]; --j; }
        a[j + 1] = x;
    }
}

void sift(std::vector<int>& a, int lo, int i, int size) {
    while (true) {
        int c = 2 * i + 1;
        if (c >= size) return;
        if (c + 1 < size && a[lo + c] < a[lo + c + 1]) ++c;
        if (a[lo + i] >= a[lo + c]) return;
        std::swap(a[lo + i], a[lo + c]);
        i = c;
    }
}

void heapsortRange(std::vector<int>& a, int lo, int hi) {
    int n = hi - lo + 1;
    for (int i = n / 2 - 1; i >= 0; --i) sift(a, lo, i, n);
    for (int end = n - 1; end > 0; --end) { std::swap(a[lo], a[lo + end]); sift(a, lo, 0, end); }
}

void medianOfThreeToLo(std::vector<int>& a, int lo, int hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] < a[lo]) std::swap(a[mid], a[lo]);
    if (a[hi] < a[lo]) std::swap(a[hi], a[lo]);
    if (a[hi] < a[mid]) std::swap(a[hi], a[mid]);
    std::swap(a[lo], a[mid]);
}

int hoarePartition(std::vector<int>& a, int lo, int hi) {
    int pivot = a[lo], i = lo - 1, j = hi + 1;
    while (true) {
        do { ++i; } while (a[i] < pivot);
        do { --j; } while (a[j] > pivot);
        if (i >= j) return j;
        std::swap(a[i], a[j]);
    }
}

void introLoop(std::vector<int>& a, int lo, int hi, int depth, int& fallbacks) {
    while (hi - lo + 1 > THRESHOLD) {
        if (depth == 0) { ++fallbacks; heapsortRange(a, lo, hi); return; }
        --depth;
        medianOfThreeToLo(a, lo, hi);
        int p = hoarePartition(a, lo, hi);
        if (p - lo < hi - p) { introLoop(a, lo, p, depth, fallbacks); lo = p + 1; }
        else { introLoop(a, p + 1, hi, depth, fallbacks); hi = p; }
    }
    insertionSort(a, lo, hi);
}

// Sorts a in place; returns the number of heapsort fallbacks. depthLimit < 0 means 2*floor(log2 n).
int introsort(std::vector<int>& a, int depthLimit = -1) {
    int n = static_cast<int>(a.size());
    if (depthLimit < 0) depthLimit = n == 0 ? 0 : 2 * (static_cast<int>(std::bit_width(static_cast<unsigned>(n))) - 1);
    int fallbacks = 0;
    introLoop(a, 0, n - 1, depthLimit, fallbacks);
    return fallbacks;
}

std::vector<int> minstd(std::uint64_t seed, int n, int mod) {
    std::vector<int> out;
    std::uint64_t x = seed;
    for (int k = 0; k < n; ++k) { x = x * 48271 % 2147483647ULL; out.push_back(static_cast<int>(x % mod)); }
    return out;
}

int main() {
    const int n = 2000;
    std::vector<int> rnd = minstd(42, n, 1000), srt(n), rev(n), eq(n, 7);
    for (int k = 0; k < n; ++k) { srt[k] = k; rev[k] = n - k; }
    for (const auto& c : std::vector<std::vector<int>>{rnd, srt, rev, eq, {}, {1}, {2, 1}}) {
        auto b = c, expect = c;
        std::sort(expect.begin(), expect.end());
        introsort(b);
        assert(b == expect);
    }
    auto b = srt; assert(introsort(b) == 0);
    b = eq; assert(introsort(b) == 0);
    b = rnd;
    auto expect = rnd;
    std::sort(expect.begin(), expect.end());
    assert(introsort(b, 0) == 1 && b == expect);
    std::cout << "ok\n";
}
const THRESHOLD = 16;

function swap(a: number[], i: number, j: number): void {
  const t = a[i]; a[i] = a[j]; a[j] = t;
}

function insertionSort(a: number[], lo: number, hi: number): void {
  for (let i = lo + 1; i <= hi; i++) {
    const x = a[i];
    let j = i - 1;
    while (j >= lo && a[j] > x) { a[j + 1] = a[j]; j--; }
    a[j + 1] = x;
  }
}

function sift(a: number[], lo: number, i: number, size: number): void {
  while (true) {
    let c = 2 * i + 1;
    if (c >= size) return;
    if (c + 1 < size && a[lo + c] < a[lo + c + 1]) c++;
    if (a[lo + i] >= a[lo + c]) return;
    swap(a, lo + i, lo + c);
    i = c;
  }
}

function heapsortRange(a: number[], lo: number, hi: number): void {
  const n = hi - lo + 1;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) sift(a, lo, i, n);
  for (let end = n - 1; end > 0; end--) { swap(a, lo, lo + end); sift(a, lo, 0, end); }
}

function medianOfThreeToLo(a: number[], lo: number, hi: number): void {
  const mid = lo + Math.floor((hi - lo) / 2);
  if (a[mid] < a[lo]) swap(a, mid, lo);
  if (a[hi] < a[lo]) swap(a, hi, lo);
  if (a[hi] < a[mid]) swap(a, hi, mid);
  swap(a, lo, mid);
}

function hoarePartition(a: number[], lo: number, hi: number): number {
  const pivot = a[lo];
  let i = lo - 1, j = hi + 1;
  while (true) {
    do { i++; } while (a[i] < pivot);
    do { j--; } while (a[j] > pivot);
    if (i >= j) return j;
    swap(a, i, j);
  }
}

/** Sorts a in place; returns the number of heapsort fallbacks. */
function introsort(a: number[], depthLimit?: number): number {
  const n = a.length;
  let depth0 = depthLimit ?? (n === 0 ? 0 : 2 * Math.floor(Math.log2(n)));
  let fallbacks = 0;
  const sort = (lo: number, hi: number, depth: number): void => {
    while (hi - lo + 1 > THRESHOLD) {
      if (depth === 0) { fallbacks++; heapsortRange(a, lo, hi); return; }
      depth--;
      medianOfThreeToLo(a, lo, hi);
      const p = hoarePartition(a, lo, hi);
      if (p - lo < hi - p) { sort(lo, p, depth); lo = p + 1; }
      else { sort(p + 1, hi, depth); hi = p; }
    }
    insertionSort(a, lo, hi);
  };
  sort(0, n - 1, depth0);
  return fallbacks;
}

function minstd(seed: number, n: number, mod: number): number[] {
  const out: number[] = [];
  let x = seed;
  for (let k = 0; k < n; k++) { x = (x * 48271) % 2147483647; out.push(x % mod); }
  return out;
}

function check(ok: boolean, msg: string): void {
  if (!ok) throw new Error("check failed: " + msg);
}
const same = (x: number[], y: number[]) => x.length === y.length && x.every((v, k) => v === y[k]);
const asc = (x: number[]) => [...x].sort((p, q) => p - q);

const n = 2000;
const rnd = minstd(42, n, 1000);
const srt = Array.from({ length: n }, (_, k) => k);
const rev = Array.from({ length: n }, (_, k) => n - k);
const eq: number[] = new Array(n).fill(7);
for (const c of [rnd, srt, rev, eq, [], [1], [2, 1]]) {
  const b = [...c];
  introsort(b);
  check(same(b, asc(c)), "sorted");
}
check(introsort([...srt]) === 0, "sorted input: no fallback");
check(introsort([...eq]) === 0, "equal input: no fallback");
const b = [...rnd];
check(introsort(b, 0) === 1 && same(b, asc(rnd)), "forced heapsort");
console.log("ok");

Variant: measure the 1.39 constant yourself

A Monte Carlo check of the indicator-variable result: average the comparison count of randomized Lomuto quicksort over 200 random permutations of 1,000 elements and compare with .

import random


def count_comparisons(a: list[int], rng: random.Random) -> int:
    comps = 0
    stack = [(0, len(a) - 1)]
    while stack:
        lo, hi = stack.pop()
        if lo >= hi:
            continue
        r = rng.randint(lo, hi)
        a[r], a[hi] = a[hi], a[r]
        pivot, i = a[hi], lo - 1
        for j in range(lo, hi):
            comps += 1
            if a[j] <= pivot:
                i += 1
                a[i], a[j] = a[j], a[i]
        a[i + 1], a[hi] = a[hi], a[i + 1]
        stack += [(lo, i), (i + 2, hi)]
    return comps


rng = random.Random(2026)
n, trials = 1000, 200
mean = sum(count_comparisons(rng.sample(range(n), n), rng) for _ in range(trials)) / trials
exact = 2 * (n + 1) * sum(1 / k for k in range(1, n + 1)) - 4 * n
print(round(mean), round(exact))
assert abs(mean - exact) / exact < 0.02

Real-world uses

  • C++ std::sort. libstdc++ (GCC) implements introsort exactly as in this lesson: median-of-3 pivot, unguarded Hoare partition, depth limit 2 * __lg(n), _S_threshold = 16 and a final insertion sort. Microsoft's STL is also introsort-based. The standard has required comparisons for std::sort since C++11, which rules out a bare quicksort.
  • Java Arrays.sort for primitives. Since Java 7 it is Yaroslavskiy's dual-pivot quicksort. The current java.util.DualPivotQuicksort claims "O(n log(n)) performance on all data sets": it switches to heapsort when its depth counter exceeds MAX_RECURSION_DEPTH = 64 * DELTA (384), merges pre-existing runs, and insertion-sorts small ranges. Object arrays use Timsort, because objects need stability.
  • Go and Rust. Go's sort.Sort and slices.Sort switched to pdqsort in Go 1.19 (2022). Rust's slice::sort_unstable was pdqsort-based from 2017 and was replaced by a newer design ("ipnsort") in 2024. Both are quicksort plus pattern detection, branch-free partitioning and a heapsort fallback; see Sorting in the Real World.
  • C qsort. The standard does not specify the algorithm. The Bentley–McIlroy design became the BSD qsort; glibc has historically preferred a merge sort when memory allows, with changes in recent releases — check your version.
  • Databases. In-memory sorts for ORDER BY, GROUP BY and sort-merge joins are commonly quicksort variants: PostgreSQL's in-memory tuple sort uses a Bentley–McIlroy-style quicksort (src/include/lib/sort_template.h) and spills to external merge sort when work_mem is exceeded. See Query Planning & Optimization and How Databases Work.
  • Selection. std::nth_element and NumPy's np.partition are introselect — quickselect with a fallback (Quickselect & Order Statistics).
  • Security. Sorting user input with a deterministic quicksort is an algorithmic complexity attack surface, like unseeded hash tables; see also Rate Limiting.

Pitfalls & edge cases

  • Sorted input with an end pivot. The most common real input is already sorted or nearly sorted (appending timestamps, re-sorting a sorted list). First- or last-element pivots make it quadratic and recurse deep. Always randomize or use median-of-3.
  • All-equal or few-distinct keys with Lomuto. Lomuto returns hi on every partition of equal keys — quadratic. Use Hoare (balanced) or three-way (linear).
  • Hoare's five traps — see the list above.
  • Recursing on both sides. Even with random pivots, a sorted-input bug or a bad RNG turns into a stack overflow at depth . Always recurse on the smaller side.
  • Inconsistent comparators. A comparator that is not a strict weak ordering (for example a.x <= b.x, or one that uses NaN-containing floats) can make unguarded scans run past the array end. Invalid comparators are a well-known cause of out-of-bounds crashes inside std::sort, whose partition is unguarded by design. Make comparators strict; handle NaN explicitly.
  • Stability assumptions. Sorting records by one key and then another relies on stability, which quicksort lacks. Java silently uses Timsort for objects for this reason; in C++ use std::stable_sort.
  • Predictable randomness. A fixed seed, or a seed an attacker can observe, makes "randomized" quicksort deterministic again. For untrusted input, seed from the OS, or use introsort and do not depend on luck at all.
  • Empty range and hi = len - 1. With unsigned index types in C++, hi = a.size() - 1 underflows on an empty vector. Use signed indices or half-open ranges.

Variations

McIlroy's killer adversary (runnable). This sorts indices with a comparator that freezes "gas" values on demand, then replays the resulting concrete array. It works against any deterministic quicksort; here, a median-of-3 Hoare-style quicksort. The asserts check that the killer input costs at least 25 times the comparisons of a random permutation at (we measured 34x; 64x at ).

import random
import sys

sys.setrecursionlimit(10000)


def quicksort_m3(a, cmp):
    """Deterministic median-of-3 quicksort. Returns the number of comparisons."""
    count = 0

    def c(x, y):
        nonlocal count
        count += 1
        return cmp(x, y)

    def sort(lo, hi):
        while hi > lo:
            mid = (lo + hi) // 2
            if c(a[mid], a[lo]) < 0: a[mid], a[lo] = a[lo], a[mid]
            if c(a[hi], a[lo]) < 0: a[hi], a[lo] = a[lo], a[hi]
            if c(a[hi], a[mid]) < 0: a[hi], a[mid] = a[mid], a[hi]
            p, i, j = a[mid], lo, hi
            while i <= j:
                while c(a[i], p) < 0: i += 1
                while c(a[j], p) > 0: j -= 1
                if i <= j:
                    a[i], a[j] = a[j], a[i]
                    i, j = i + 1, j - 1
            if j - lo < hi - i:
                sort(lo, j); lo = i
            else:
                sort(i, hi); hi = j

    sort(0, len(a) - 1)
    return count


def killer_input(n, sorter):
    gas = n
    val = [gas] * n
    nsolid, candidate = 0, -1

    def cmp(x, y):
        nonlocal nsolid, candidate
        if val[x] == gas and val[y] == gas:      # both unknown: freeze one
            z = x if x == candidate else y
            val[z] = nsolid
            nsolid += 1
        if val[x] == gas:
            candidate = x
        elif val[y] == gas:
            candidate = y
        return val[x] - val[y]

    sorter(list(range(n)), cmp)
    for i in range(n):                           # never-frozen items: any larger distinct values
        if val[i] == gas:
            val[i] = nsolid
            nsolid += 1
    return val


num = lambda x, y: (x > y) - (x < y)
n = 2000
bad = killer_input(n, quicksort_m3)
c_bad = quicksort_m3(list(bad), num)
c_rand = quicksort_m3(random.Random(7).sample(range(n), n), num)
print(c_bad, c_rand)
assert c_bad > 25 * c_rand and c_bad > n * n // 5

Dual-pivot quicksort. Choose and partition into < p1, p1..p2, > p2 in one pass with three indices (lt, i, gt), then recurse three ways. Each element is compared with first and, only if it is not smaller, with , which is why the expected comparison count drops a little. The real gain on modern CPUs is fewer passes over memory: splitting three ways means fewer recursion levels, so each element is scanned fewer times, which Kushagra et al. (ALENEX 2014) argue explains the speed-up better than comparison counts do. Yaroslavskiy's version is in Java's JDK; the analysis is Wild and Nebel's.

def dual_pivot_quicksort(a: list[int], lo: int = 0, hi: int | None = None) -> list[int]:
    """Yaroslavskiy-style partition with pivots a[lo] <= a[hi]."""
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return a
    if a[lo] > a[hi]:
        a[lo], a[hi] = a[hi], a[lo]
    p1, p2 = a[lo], a[hi]
    lt, i, gt = lo + 1, lo + 1, hi - 1
    while i <= gt:
        if a[i] < p1:
            a[i], a[lt] = a[lt], a[i]
            lt += 1
        elif a[i] > p2:
            while a[gt] > p2 and i < gt:
                gt -= 1
            a[i], a[gt] = a[gt], a[i]
            gt -= 1
            if a[i] < p1:
                a[i], a[lt] = a[lt], a[i]
                lt += 1
        i += 1
    lt -= 1
    gt += 1
    a[lo], a[lt] = a[lt], a[lo]
    a[hi], a[gt] = a[gt], a[hi]
    dual_pivot_quicksort(a, lo, lt - 1)
    dual_pivot_quicksort(a, lt + 1, gt - 1)
    dual_pivot_quicksort(a, gt + 1, hi)
    return a


import random
rng = random.Random(1)
for trial in range(200):
    xs = [rng.randint(0, 20) for _ in range(rng.randint(0, 60))]
    assert dual_pivot_quicksort(list(xs)) == sorted(xs)
print("ok")

Quickselect. Partition once, then recurse only into the side that contains index : expected , the engine of nth_element. See Quickselect & Order Statistics.

Pattern-defeating quicksort (pdqsort). Orson Peters (2021, arXiv:2106.05123) combines introsort with: insertion sort on small ranges, ninther pivots on large ones, detection of already-partitioned ranges (sorted input becomes ), shuffling a few elements after a bad partition to break adversarial patterns, branch-free block partitioning from BlockQuicksort, and three-way handling when the pivot equals its predecessor. Details in Sorting in the Real World.

Multi-key string quicksort (Bentley and Sedgewick, 1997) three-way partitions on one character at a time — the bridge to MSD radix sort.

Parallel, stable and linked-list quicksort. The two recursive calls are independent, so they parallelise trivially; the partition itself is the bottleneck. Partitioning into a buffer makes quicksort stable but not in place, and partitioning a linked list into three relinked lists needs no random access — in both cases merge sort is usually the better choice.

Practice ladder

Easy → hard. Descriptions are paraphrased; follow the links for the exact statements.

  1. Quicksort 1 – Partition (HackerRank) — split an array around its first element into left, equal and right parts. Teaches the partition contract without in-place mechanics.
Hint

Three lists and one pass. Then ask yourself how to do the same with zero extra arrays: that is the rest of this ladder.

  1. Quicksort In-Place (HackerRank) — implement Lomuto partition with the last element as pivot and print the array after each partition. Teaches exact Lomuto mechanics; your output must match swap-for-swap.
Hint

Use the trace table above as a test case. Print after the final pivot swap, recurse left before right.

  1. Running Time of Quicksort (HackerRank) — count insertion-sort shifts versus Lomuto swaps on the same array and report the difference. Teaches that swap counts are a real cost and differ by algorithm.
Hint

Insertion-sort shifts equal the number of inversions. Lomuto swaps include the self-swaps when i == j and the final pivot swap — check the problem's convention.

  1. Sort Array By Parity (LeetCode 905) — move all even numbers before all odd numbers. Teaches that a partition is just a predicate split; Hoare-style converging scans do it in one pass.
Hint

i from the left stops at an odd number, j from the right stops at an even number; swap while i < j.

Solution
def sort_array_by_parity(nums: list[int]) -> list[int]:
    i, j = 0, len(nums) - 1
    while i < j:
        while i < j and nums[i] % 2 == 0:
            i += 1
        while i < j and nums[j] % 2 == 1:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    return nums


out = sort_array_by_parity([3, 1, 2, 4])
assert all(x % 2 == 0 for x in out[:2]) and all(x % 2 == 1 for x in out[2:])
assert sort_array_by_parity([]) == [] and sort_array_by_parity([1]) == [1]
print("ok")

time, space, at most swaps.

  1. Sort Colors (LeetCode 75) — sort an array of 0s, 1s and 2s in one pass in place. Teaches Dijkstra's three-way partition with pivot value 1.
Hint

partition3 with p = 1 and lt = 0, i = 0, gt = n - 1. When you swap with gt, do not advance i.

Solution
def sort_colors(nums: list[int]) -> None:
    lt, i, gt = 0, 0, len(nums) - 1
    while i <= gt:
        if nums[i] == 0:
            nums[lt], nums[i] = nums[i], nums[lt]
            lt += 1
            i += 1
        elif nums[i] == 2:
            nums[i], nums[gt] = nums[gt], nums[i]
            gt -= 1
        else:
            i += 1


for xs in ([2, 0, 2, 1, 1, 0], [2, 0, 1], [0], [], [2, 2, 2], [1, 0]):
    ys = list(xs)
    sort_colors(ys)
    assert ys == sorted(xs)
print("ok")

time, one pass, space.

  1. Partition Array According to Given Pivot (LeetCode 2161) — three-way partition that must keep the original relative order in each part. Teaches why in-place quicksort partitions are not stable, and what stability costs ( extra space).
Hint

Three passes (or three output lists): less, equal, greater, each in input order.

  1. Sort an Array (LeetCode 912) — sort integers without the built-in sort in . Teaches that a textbook quicksort is not enough: the test data is reported to include large sorted and many-duplicate arrays that time out last-element-pivot Lomuto.
Hint

Random pivot plus three-way partition handles both sorted and duplicate-heavy inputs. Recurse on the smaller side.

Solution
import random


def sort_array(nums: list[int]) -> list[int]:
    rng = random.Random()
    a = nums

    def sort(lo: int, hi: int) -> None:
        while lo < hi:
            r = rng.randint(lo, hi)
            a[lo], a[r] = a[r], a[lo]
            p, lt, i, gt = a[lo], lo, lo + 1, hi
            while i <= gt:
                if a[i] < p:
                    a[lt], a[i] = a[i], a[lt]; lt += 1; i += 1
                elif a[i] > p:
                    a[i], a[gt] = a[gt], a[i]; gt -= 1
                else:
                    i += 1
            if lt - lo < hi - gt:
                sort(lo, lt - 1); lo = gt + 1
            else:
                sort(gt + 1, hi); hi = lt - 1

    sort(0, len(a) - 1)
    return a


assert sort_array([5, 2, 3, 1]) == [1, 2, 3, 5]
assert sort_array([5, 1, 1, 2, 0, 0]) == [0, 0, 1, 1, 2, 5]
big = list(range(50000))
assert sort_array(list(big)) == big
assert sort_array([3] * 50000) == [3] * 50000
print("ok")

Expected on every input, when all keys are equal, stack.

  1. Kth Largest Element in an Array (LeetCode 215) — find the k-th largest without fully sorting. Teaches quickselect: one partition, recurse on one side, expected .
Hint

The k-th largest is the element at index n - k in sorted order. Partition; if the pivot lands at that index you are done, otherwise loop into the side that contains it. Use three-way partition — the judge has many-duplicate cases.

Solution
import random


def find_kth_largest(nums: list[int], k: int) -> int:
    a, target = list(nums), len(nums) - k
    lo, hi = 0, len(a) - 1
    rng = random.Random(0)
    while True:
        r = rng.randint(lo, hi)
        a[lo], a[r] = a[r], a[lo]
        p, lt, i, gt = a[lo], lo, lo + 1, hi
        while i <= gt:
            if a[i] < p:
                a[lt], a[i] = a[i], a[lt]; lt += 1; i += 1
            elif a[i] > p:
                a[i], a[gt] = a[gt], a[i]; gt -= 1
            else:
                i += 1
        if target < lt:
            hi = lt - 1
        elif target > gt:
            lo = gt + 1
        else:
            return p


assert find_kth_largest([3, 2, 1, 5, 6, 4], 2) == 5
assert find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4
assert find_kth_largest([1] * 1000, 500) == 1
print("ok")

Expected time ( comparisons in expectation with a random pivot), extra space beyond the copy.

  1. K Closest Points to Origin (LeetCode 973) — return any k points nearest the origin. Teaches quickselect on a derived key (squared distance, no sqrt) and that the output need not be sorted.
Hint

Partition points by x*x + y*y around a random pivot until the pivot's final index is k - 1 or k; return the first k.

  1. Nuts & Bolts Problem (LintCode 399) — match nuts to bolts when you may only compare a nut with a bolt. Teaches using a partition of one set to pick the pivot for the other: expected.
Hint
Pick a bolt, partition the nuts around it, which reveals the matching nut; partition the bolts around that nut. Both arrays are now split at the same position; recurse on both halves.
  1. Sort List (LeetCode 148) — sort a linked list in . Teaches when quicksort is the wrong tool: you can quicksort a list with a three-list partition, but merge sort needs no random pivot and has no bad case.
Hint
Implement both: three-list quicksort (head as pivot after shuffling values, or a random walk to pick one) and bottom-up merge sort. Time them on a sorted list.
  1. Wiggle Sort II (LeetCode 324) — reorder so that nums[0] < nums[1] > nums[2] < …, ideally in time and space. Teaches quickselect for the median plus a three-way partition through a virtual index mapping. Hard.
Hint
Find the median with quickselect. Then three-way partition around it, but address position `i` as `(1 + 2*i) % (n | 1)`, so larger elements land on odd indices and smaller on even ones, with medians spread apart.
Solution
```python
import random


def wiggle_sort(nums: list[int]) -> None:
    n = len(nums)
    if n < 2:
        return
    # 1. median by quickselect (on a copy, to keep the code short)
    a, k, lo, hi = list(nums), n // 2, 0, n - 1
    rng = random.Random(0)
    while True:
        r = rng.randint(lo, hi)
        a[lo], a[r] = a[r], a[lo]
        p, lt, i, gt = a[lo], lo, lo + 1, hi
        while i <= gt:
            if a[i] < p:
                a[lt], a[i] = a[i], a[lt]; lt += 1; i += 1
            elif a[i] > p:
                a[i], a[gt] = a[gt], a[i]; gt -= 1
            else:
                i += 1
        if k < lt: hi = lt - 1
        elif k > gt: lo = gt + 1
        else: break
    median = p
    # 2. 3-way partition with virtual indexing: big values to odd slots first
    idx = lambda i: (1 + 2 * i) % (n | 1)
    left, i, right = 0, 0, n - 1
    while i <= right:
        if nums[idx(i)] > median:
            nums[idx(left)], nums[idx(i)] = nums[idx(i)], nums[idx(left)]
            left += 1; i += 1
        elif nums[idx(i)] < median:
            nums[idx(right)], nums[idx(i)] = nums[idx(i)], nums[idx(right)]
            right -= 1
        else:
            i += 1


def is_wiggle(xs):
    return all((xs[i] < xs[i + 1]) if i % 2 == 0 else (xs[i] > xs[i + 1]) for i in range(len(xs) - 1))


rng = random.Random(5)
for xs in ([1, 5, 1, 1, 6, 4], [1, 3, 2, 2, 3, 1], [4, 5, 5, 6]):
    ys = list(xs); wiggle_sort(ys); assert is_wiggle(ys) and sorted(ys) == sorted(xs), ys
for _ in range(300):              # random inputs that admit a wiggle ordering
    m = rng.randint(1, 12)
    xs = [rng.randint(0, 5) for _ in range(m)]
    s = sorted(xs)
    half = (m + 1) // 2
    cand = [0] * m
    cand[::2], cand[1::2] = s[:half][::-1], s[half:][::-1]
    if not is_wiggle(cand):
        continue
    ys = list(xs); wiggle_sort(ys); assert is_wiggle(ys), (xs, ys)
print("ok")
```

Expected <span class="math" data-tex="O(n)"></span> time; <span class="math" data-tex="O(1)"></span> extra space if the quickselect is done in place on `nums` itself.

Common mistakes & interview follow-ups

"What is quicksort's worst case, and when does it happen?" , when every pivot is the minimum or maximum of its subarray. With a first/last pivot that means sorted or reverse-sorted input (and all-equal input with Lomuto). With random pivots it requires a run of bad luck whose probability vanishes super-polynomially. Say both halves.

"Why is quicksort faster than merge sort in practice if it does more comparisons?" It does fewer data moves (Hoare: about swaps versus moves for merge sort), works in place so the working set is half the size, and its sequential scans are cache- and prefetch-friendly. Merge sort's advantage is stability and the worst-case guarantee.

"How do you make the worst case ?" Introsort: depth limit , heapsort fallback. Or median of medians for the pivot, which is correct but slower in practice. Mention that this is what std::sort does.

"How much stack? Many duplicates? Stable?" stack with smaller-side recursion, independent of time. Duplicates: Lomuto goes quadratic, Hoare stays balanced, three-way makes it . Stability needs extra space, so use merge sort.

"What if the data does not fit in memory?" Quicksort's random access pattern across the whole array is a poor fit for disk. Use external merge sort: sort memory-sized runs (with quicksort, fine) and merge them. See Sorting in the Real World.

"What if an attacker controls the input?" Deterministic pivots are attackable — McIlroy's adversary breaks any of them via the comparator. Use introsort, or a random pivot seeded unpredictably.

"Why 2 * floor(log2 n) for the depth limit?" A typical element sits at depth about in the recursion, and with median-of-3 pivots and a 16-element cutoff even the deepest path rarely exceeds on normal data, yet the budget caps the quicksort work at . Musser's paper uses this value; any constant multiple of preserves the bound.

"Find the k-th smallest element." Quickselect, expected ; median of medians for an worst case.

Quick quiz

1. Lomuto partition on [3, 3, 3, 3]: what index does it return, and what does that imply for quicksort on equal keys?

Answer

It returns 3 (hi): every element satisfies a[j] <= pivot, so i ends at hi - 1 and the pivot stays at hi. The left side has elements, so quicksort makes comparisons — quadratic. Hoare would split it in the middle; three-way partition would finish in one pass.

2. In Hoare's scheme with pivot a[lo], why must the recursive calls be on [lo, j] and [j+1, hi] and not [lo, j-1] and [j+1, hi]?

Answer

Hoare returns a split point, not the pivot's position. a[j] is some element of the left side (in the trace, a[5] = 3 while the pivot was 7). Excluding it leaves an element that is never sorted relative to its neighbours.

3. In the expected-comparisons proof, why are and (the minimum and maximum) compared with probability only ?

Answer

They are compared only if one of them is the first pivot chosen from — the whole array. Any other first pivot separates them forever. Two favourable choices out of : probability .

4. A quicksort with random pivots recursing on both sides sorts items. What is the worst-case stack depth, and how do you reduce it to about 20?

Answer

Worst case frames (every pivot extreme). Recursing only into the smaller side and looping on the larger bounds the depth by , whatever the pivots.

5. Introsort's quicksort phase ends and heapsort takes over on subarrays of sizes 100, 5,000 and 20 in an array of 10,000. Why is the total heapsort work still ?

Answer

The subarrays are disjoint, so their sizes sum to at most , and .

Further reading / sources

  • C. A. R. Hoare, "Algorithm 64: Quicksort", Communications of the ACM 4(7), 1961; and "Quicksort", The Computer Journal 5(1), 1962 — the original algorithm and analysis.
  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 4th ed. — Chapter 7 (Lomuto partition, randomized quicksort, the indicator-variable analysis in §7.4), Problem 7-1 (Hoare partition correctness), Problem 7-4 (stack depth).
  • Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed. — §2.3 (quicksort, three-way partitioning, entropy-optimal sorting); Sedgewick, "The Analysis of Quicksort Programs", Acta Informatica 7, 1977.
  • Donald E. Knuth, The Art of Computer Programming, Vol. 3, §5.2.2 — exact analysis including median-of-3.
  • Jon L. Bentley and M. Douglas McIlroy, "Engineering a Sort Function", Software: Practice and Experience 23(11), 1993 — ninther, Bentley–McIlroy three-way partition.
  • M. Douglas McIlroy, "A Killer Adversary for Quicksort", Software: Practice and Experience 29(4), 1999.
  • David R. Musser, "Introspective Sorting and Selection Algorithms", Software: Practice and Experience 27(8), 1997.
  • Sebastian Wild and Markus E. Nebel, "Average Case Analysis of Java 7's Dual Pivot Quicksort", ESA 2012; Kushagra, López-Ortiz, Qiao, Munro, "Multi-Pivot Quicksort: Theory and Experiments", ALENEX 2014.
  • Stefan Edelkamp and Armin Weiß, "BlockQuicksort: Avoiding Branch Mispredictions in Quicksort", ESA 2016.
  • Orson R. L. Peters, "Pattern-defeating Quicksort", 2021, arXiv:2106.05123.
  • Scott A. Crosby and Dan S. Wallach, "Denial of Service via Algorithmic Complexity Attacks", USENIX Security 2003.
  • OpenJDK source, java.util.DualPivotQuicksort; GCC libstdc++ source, bits/stl_algo.h (__introsort_loop).

Lessons: previous — Merge Sort & Inversion Counting · next — Heap Sort · module — Searching & Sorting · course map.

Related Archon pages: Sorting & Searching (overview) · Two Pointers · Quickselect & Order Statistics · Sorting in the Real World · Non-Comparison Sorts · Probability for Engineers · Recursion & Induction · Data Structures in Memory.