Quick Sort

Quicksort is the sort most language standard libraries reach for first (with a merge-sort or insertion-sort fallback for edge cases). It sorts in place, has tiny constant overhead, and averages $O(n \log n)$ — but unlike merge sort, its worst case is a real $O(n^2)$ that shows up on ordinary-looking input if you’re not careful about pivot choice.

What you’ll learn

• Partitioning — the one operation quicksort is built from — via the Lomuto scheme, plus a look at the alternative Hoare scheme.
• Recursive, in-place quicksort.
• Why picking the last element as pivot turns an already-sorted array into the $O(n^2)$ worst case.
• The randomized pivot fix, and why it makes the worst case vanishingly unlikely in practice.
• Why quicksort is not stable, and when that matters.

The cue

Nobody asks you to implement quicksort. They ask for the thing it is built from.

You are looking at a partition when…

• You need the kth smallest or largest element and a full sort is overkill — quickselect is one partition, recursing on one side only.
• The task is to rearrange in place by a predicate: move all zeros to the end, sort colours, separate evens from odds. That is a partition with the pivot replaced by a test. LC 75, 283, 905.
• Values fall into three groups and you want one pass — Dutch national flag, LC 75.
• An interviewer says “in place, $O(1)$ extra space” about a rearrangement. Partitioning is the in-place primitive.

When it is the wrong tool. If you need stability, quicksort is out — see the pitfalls below. If you need a guaranteed $O(n \log n)$, use merge sort or heap sort; quicksort’s worst case is $O(n^2)$ and randomisation makes it unlikely, not impossible. And in real Python code, list.sort() beats any hand-written quicksort by a wide margin — this page is about understanding the machine, not about beating it.

Partitioning: the Lomuto scheme

Partitioning rearranges a subarray around a chosen pivot value so that everything $\le$ the pivot ends up to its left, everything greater ends up to its right, and the pivot lands in its final, correctly-sorted position. Everything else in quicksort is just “partition, then recurse on both halves.”

The Lomuto scheme picks the last element as the pivot and walks the array with two indices: j scans left to right, i tracks the boundary of the “elements seen so far that are $\le$ pivot” region.

lomuto_partition.py

def partition(arr, low, high):
    pivot = arr[high]          # last element as pivot
    i = low - 1                # boundary of the "<= pivot" region
 
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
 
    arr[i + 1], arr[high] = arr[high], arr[i + 1]   # drop pivot into place
    return i + 1                                     # pivot's final index
 
 
arr = [8, 3, 1, 7, 0, 2]
p = partition(arr, 0, len(arr) - 1)
print("after one partition:", arr)
print("pivot landed at index:", p)

Run it: everything left of the returned index is $\le 2$, everything right of it is $> 2$ — the pivot itself sits between them, already in its correct sorted spot. That’s the whole trick, repeated recursively.

The Hoare partition scheme

Tony Hoare’s original scheme (from 1962) uses two pointers closing in from both ends, swapping out-of-place pairs as it goes, and does roughly 3x fewer swaps than Lomuto on average. Its downside: the index it returns is not the pivot’s final position (it’s just a split point), which makes the recursion slightly less intuitive to write correctly. Lomuto is what most textbooks and interviews use because it’s easier to reason about — Hoare is what many production implementations actually use, for the speed.

Recursive quicksort, in place

Quicksort partitions the whole array, then recursively quicksorts the left and right sides of the pivot. There’s no merge step (unlike merge sort) — once both sides are sorted, the whole array is sorted, because partitioning already guaranteed the pivot’s position relative to everything else.

quicksort_inplace.py

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1
 
 
def quicksort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        p = partition(arr, low, high)
        quicksort(arr, low, p - 1)      # everything <= pivot
        quicksort(arr, p + 1, high)     # everything > pivot
    return arr
 
 
nums = [8, 3, 1, 7, 0, 10, 2, 5]
print("sorted:", quicksort(nums))

No extra array is allocated — every swap happens directly inside arr. Only the recursion’s call stack uses extra space.

Watch a single partition step by step

sketch Lomuto partition around a pivot p5.js Pause Restart

j scans left to right. Any element <= the pivot (last element, shown in amber) gets swapped into the growing 'smaller' region tracked by i. The final swap drops the pivot into its correct sorted position.

Why pivot choice matters: the O(n^2) trap

Lomuto’s partition always picks the last element as pivot. If the input is already sorted (or reverse-sorted), that pivot is always the largest (or smallest) remaining value — partitioning splits the array into a piece of size 0 and a piece of size n - 1, every single time.

worst_case_demo.py

def partition(arr, low, high, counter):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        counter[0] += 1   # count comparisons
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1
 
 
def quicksort(arr, low, high, counter):
    if low < high:
        p = partition(arr, low, high, counter)
        quicksort(arr, low, p - 1, counter)
        quicksort(arr, p + 1, high, counter)
 
 
sorted_input = list(range(200))       # already sorted -- the worst case
counter = [0]
quicksort(sorted_input, 0, len(sorted_input) - 1, counter)
print(f"n=200, already sorted: {counter[0]} comparisons")
print(f"n^2 would be {200 * 200}, n*log2(n) would be about {int(200 * 7.6)}")

That comparison count lands right on $n(n-1)/2$ — quadratic, not log-linear. Recursing into a 0-and-(n-1) split at every level also means the recursion goes n levels deep instead of $\log n$, which on a truly pathological input can blow the call stack too.

The fix: pick the pivot randomly

The failure mode above only happens because the pivot is picked by a fixed rule (always “last element”) that an input can be crafted to defeat. Picking the pivot uniformly at random before partitioning breaks that: no fixed input can reliably trigger the bad split anymore, because the “unlucky” pivot is a different, unpredictable index every run.

randomized_quicksort.py

import random
 
 
def partition(arr, low, high):
    # swap a random element into the pivot slot before partitioning as usual
    rand_idx = random.randint(low, high)
    arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
 
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1
 
 
def quicksort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        p = partition(arr, low, high)
        quicksort(arr, low, p - 1)
        quicksort(arr, p + 1, high)
    return arr
 
 
already_sorted = list(range(15))
print("random-pivot quicksort:", quicksort(already_sorted))

The worst case is still technically $O(n^2)$ — an adversary who can see your random seed could still construct a bad case — but for any fixed input, the expected running time is $O(n \log n)$. This is the standard production fix; some libraries instead pick the median of three (first, middle, last elements) as a cheaper, deterministic-ish alternative.

Not stable, and why it doesn’t need extra memory

Quicksort partitions in place by swapping elements directly inside the input array, so it needs no auxiliary array (unlike merge sort’s $O(n)$ buffer) — only $O(\log n)$ extra space for the recursion stack on average. The tradeoff: swapping equal elements past each other during partitioning can change their relative order, so quicksort is not stable.

Dry run

One Lomuto partition of [8, 3, 1, 7, 0, 2], pivot 2

i is the boundary of the “seen so far and $\le$ pivot” region; j scans.

j	arr[j]	vs pivot 2	Action	Array after
0	8	greater	skip	[8, 3, 1, 7, 0, 2]
1	3	greater	skip	[8, 3, 1, 7, 0, 2]
2	1	$\le$	i -> 0, swap i,j	[1, 3, 8, 7, 0, 2]
3	7	greater	skip	[1, 3, 8, 7, 0, 2]
4	0	$\le$	i -> 1, swap i,j	[1, 0, 8, 7, 3, 2]
—	—	—	place pivot: swap 2 and 5	[1, 0, 2, 7, 3, 8]

Returns index 2. Everything left of it (1, 0) is $\le 2$; everything right (7, 3, 8) is $> 2$ — checked programmatically, not by eye.

Three things worth naming:

• Neither side comes out sorted. The left is [1, 0], still wrong. Partitioning does not sort; it places one element and splits the rest. That single placed element is what makes the recursion legitimate — index 2 never needs to move again.
• i lags behind j. They coincide only while every scanned element is small. The gap between them is exactly the count of large elements seen so far, which is why the final swap lands the pivot at i + 1.
• Elements greater than the pivot are never touched during the scan — they only move when a later small element swaps past them. That is why Lomuto does more swaps than Hoare on average while being far easier to reason about.

The $O(n^2)$ trap, counted

Sorted input with a last-element pivot means every partition peels off exactly one element.

n	Comparisons	Recursion depth	$n(n-1)/2$
10	45	9	45
20	190	19	190
50	1,225	49	1,225

The comparison count hits $n(n-1)/2$ exactly at every size — not approximately, exactly. And the recursion depth is n - 1, which matters more than the time in Python: at n = 10{,}000 that is 10,000 stack frames against CPython’s ~1,000 limit, so the failure is a RecursionError, not a slow sort.

With one random.randint(low, high) before each partition, five runs each:

n	Randomised comparisons	Randomised depth
10	20, 22, 21, 21, 19	3-4
20	58, 77, 68, 87, 84	5-9
50	230, 251, 255, 242, 246	8-10

At n = 50: ~245 comparisons instead of 1,225, and depth ~9 instead of 49. Sorted input is one of the most common shapes in a test suite, so this is not a hypothetical.

Quicksort is not stable

Sorting [(1, 'a'), (1, 'b'), (0, 'c')] by the first element:

Method	Result
Lomuto quicksort	[(0, 'c'), (1, 'b'), (1, 'a')]
sorted(..., key=...)	[(0, 'c'), (1, 'a'), (1, 'b')]

'a' and 'b' come out swapped. Both orderings are correctly sorted by key; only one preserves the input order of equal elements. The long-range swaps that make quicksort fast are exactly what destroys stability — an element can jump past an equal element it never compared against.

This is why Python’s sorted is not quicksort. If a problem sorts by one key and relies on a previous ordering surviving, quicksort silently gives a different (still “sorted”) answer.

Pitfalls

• A fixed pivot on sorted input. Last-element pivot on [1..n] costs exactly $n(n-1)/2$ comparisons and n - 1 stack frames — 1,225 and 49 at n = 50, measured. One random.randint(low, high) before partitioning drops that to ~245 and depth ~9.
• In Python the depth is the real danger, not the time. n - 1 frames means a RecursionError at around 1,000 elements of adversarial input, well before the quadratic time becomes the visible problem.
• Assuming quicksort is stable. It is not: [(1,'a'), (1,'b'), (0,'c')] comes back with 'a' and 'b' swapped. If equal elements must keep their relative order, use merge sort or sorted.
• Using < instead of <= in the partition test. With <, elements equal to the pivot pile up on the right, so an array of all-equal values produces maximally unbalanced splits — $O(n^2)$ on [5]*n. A three-way (Dutch flag) partition is the real fix when duplicates are common.
• Forgetting that Hoare’s returned index is not the pivot’s final position. It is a split point, so the recursion is go(low, p) and go(p+1, high) — not p-1/p+1 as with Lomuto. Mixing the two conventions gives an infinite recursion or a dropped element.
• Recursing on the larger side first. Recurse into the smaller partition and loop on the larger (tail-call elimination by hand) to bound stack depth at $O(\log n)$ even on bad splits.
• Swapping when i == j. Harmless but wasted work — in the traced partition it happens whenever the scan has seen no large elements yet. Worth a guard only if you are counting swaps.
• Claiming $O(\log n)$ space unconditionally. It is $O(\log n)$ expected and $O(n)$ worst case, because the space is the recursion stack. The same randomisation that fixes the time fixes this.

Time and space complexity

Case	Complexity	Why
Best	$O(n \log n)$	Pivot splits the array roughly in half each time
Average	$O(n \log n)$	True for random pivots and random or randomized input
Worst	$O(n^2)$	Pivot is always the min/max — one side of the split is empty
Space	$O(\log n)$ average, $O(n)$ worst	Recursion call stack depth
Stable?	No	Partitioning can reorder equal elements

The variant map

Variant	The change	Canonical problem
Quickselect	Recurse on one side only, chosen by comparing the pivot index with k	215 · 973
Three-way (Dutch flag) partition	Split into <, ==, > — the equal block finishes in one pass	75 Sort Colors
Partition by a predicate	Replace “compare to pivot” with any boolean test	905 Sort Array By Parity · 283 Move Zeroes
Hoare partition	Two pointers closing from both ends; returns a split point, so recurse (low, p) and (p+1, high)	production implementations
Randomised pivot	One random.randint(low, high) swap before partitioning	mandatory, not optional
Median-of-three pivot	Pivot = median of first, middle, last — cheap protection against sorted input	classic C++ qsort
Introsort	Quicksort, switching to heap sort past a depth limit — guaranteed $O(n \log n)$	C++ std::sort
Insertion sort for small subarrays	Stop recursing below ~10-16 elements and insertion-sort the whole thing once	every real implementation
Recurse smaller side, loop larger	Bounds stack depth at $O(\log n)$ even on bad splits	—

Introsort is the honest answer to “quicksort’s worst case”

std::sort is not quicksort. It is introsort: run quicksort, track the recursion depth, and once it exceeds roughly $2 \log_2 n$, switch that subtree to heap sort. You keep quicksort’s constant factor in the common case and inherit heap sort’s $O(n \log n)$ guarantee in the bad case.

That is a better answer than “randomise the pivot”, because randomisation makes the worst case unlikely rather than impossible. Naming introsort shows you know the difference.

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 2161 — Partition Array According to Given Pivot · Medium

Problem. Rearrange nums so that every value less than pivot comes first, then every value equal to pivot, then every value greater — and the relative order within the less-than and greater-than groups must be preserved.

Constraints. 1 <= len(nums) <= 10^5, -10^6 <= nums[i] <= 10^6, and pivot occurs in nums.

Examples. nums = [9,12,5,10,14,3,10], pivot = 10 gives [9,5,3,10,10,12,14] · nums = [-3,4,3,2], pivot = 2 gives [-3,2,4,3]

pch.exerciseTag pch.exerciseTitle

Editorial

The requirement that relative order be preserved is what makes this interesting. Quicksort’s in-place partition works by swapping distant elements, which destroys order — it is not stable. So the Dutch national flag approach from LC 75, which is the obvious reach, gives a wrong answer here.

Time $O(n)$ — three linear passes. Space $O(n)$.

The three-comprehension solution is $O(n)$ and obviously stable. A single pass with two write pointers (one from each end) is also possible but only if you fill the less group forward and the greater group backward and then reverse the greater part — more code for the same complexity.

[-3,4,3,2] with pivot = 2 shows the stability requirement clearly: 4 appears before 3 in the input, and must still do so in the output even though 3 < 4.

Follow-ups: “Do it in place?” — not while preserving order without extra work; say so explicitly, since it is the crux. “Why can’t you use the Dutch flag partition?” — it is unstable; this is the expected question. “What if order did not matter?” — then LC 75’s in-place three-way partition is ideal at $O(1)$ space.

LC 462 — Minimum Moves to Equal Array Elements II · Medium

Problem. In one move you may increment or decrement any element by 1. Return the minimum number of moves to make all elements equal.

Constraints. 1 <= len(nums) <= 10^5, -10^9 <= nums[i] <= 10^9.

Examples. [1,2,3] gives 2 · [1,10,2,9] gives 16

pch.exerciseTag pch.exerciseTitle

Editorial

The cost of choosing target t is $\sum |n_i - t|$, and that sum is minimised at the median — not the mean, which minimises squared deviation instead. Confusing the two is the standard mistake.

Time $O(n \log n)$ for the sort. Space $O(1)$ beyond the sort.

Why the median? Imagine moving t slightly upward. Every element below t costs one more, every element above costs one less, so the net change is (count below) - (count above). That is zero exactly when the counts balance — i.e. at the median. For an even-length array any value between the two middle elements is optimal, which is why nums[n // 2] works without averaging.

[1,10,2,9] gives 16 with either middle value (9 or 2 as the target both give 16), confirming the plateau.

Since only the median is needed, quickselect finds it in $O(n)$ average without a full sort — the direct connection to this page, and the answer if asked to beat $O(n \log n)$.

Follow-ups: “Prove the median is optimal” — the balance argument above; the most likely follow-up. ”$O(n)$?” — quickselect. “Only increments allowed (LC 453)?” — different: the answer is sum(nums) - n * min(nums). “Minimise squared distance?” — then it is the mean.

LC 969 — Pancake Sorting · Medium

Problem. You may only reverse a prefix of the array (a “flip”). Return any sequence of flip sizes that sorts the array, using at most 10 * len(arr) flips.

Constraints. 1 <= len(arr) <= 100, arr is a permutation of 1..len(arr).

Examples. [3,2,4,1] gives a valid flip sequence such as [4,2,4,3] · [1,2,3] gives []

Why this test replays your flips

Many flip sequences are valid, so the test applies your flips to the input and checks the array ends up sorted — and that every flip size is in range. Any correct sequence passes.

pch.exerciseTag pch.exerciseTitle

Editorial

The only permitted operation is a prefix reversal, which rules out ordinary swapping. But selection sort adapts neatly: bring the largest unplaced value to the front with one flip, then flip the whole unsorted prefix to send it to the back of that prefix — its final home.

Time $O(n^2)$ — each round scans for a maximum. Flips at most 2n, well inside the 10n budget. Space $O(1)$ beyond the output.

Three cases save flips and are worth handling:

• Already at the end (idx == size - 1) — no flips needed at all.
• Already at the front (idx == 0) — skip the first flip.
• Sorted input — returns [], which is valid.

A flip of size 1 is a no-op, which is why the idx != 0 guard avoids emitting one.

[1,2,3] returning an empty list is a good check that you are not flipping unconditionally.

Follow-ups: “Minimise the flip count?” — that is the pancake number problem, NP-hard in general and unsolved for large n; the greedy 2n bound is what is expected. “Why does two flips suffice per element?” — one to the front, one to the target. “Burnt pancake variant?” — each flip also inverts the pieces, making it harder.

Practice

Nobody asks you to implement quicksort in an interview — they ask for the partition it is built on. These are the problems where partitioning is the answer: selection without a full sort, and the in-place rearrangement that comes with it.

8 problems

1 easy7 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○1051Height Checkereasy
• ○347Top K Frequent ElementsmediumNeetCode 150Blind 75amazonmetauberbytedance
• ○147Insertion Sort Listmedium
• ○215Kth Largest Element in an ArraymediumNeetCode 150LeetCode Top Interview 150
• ○324Wiggle Sort IImedium
• ○692Top K Frequent Wordsmedium
• ○912Sort an Arraymedium
• ○973K Closest Points to OriginmediumNeetCode 150

Self-check

pch.quizTag pch.quizDefaultTitle

1. After one Lomuto partition of [8,3,1,7,0,2] the array is [1,0,2,7,3,8] and the return value is 2. What is guaranteed?

   A Both halves are sorted B Only index 2 is final: everything left of it is <= 2, everything right is > 2, and neither side is sorted C The array is sorted up to index 2 D The pivot was the median
   pch.quizShowAnswer

   B — Only index 2 is final: everything left of it is <= 2, everything right is > 2, and neither side is sorted — The left side is [1, 0] -- still out of order. Partitioning places exactly one element permanently and splits the rest into two independent subproblems. That single placement is what makes the recursion valid, and it is also what quickselect exploits to discard a whole side.

2. Last-element pivot on an already-sorted array of 50 elements. What does it cost?

   A About 50 log 50, roughly 280 comparisons B Exactly 1,225 comparisons -- n(n-1)/2 -- and recursion depth 49 C It raises immediately on the first partition D The same as random input; sorted order does not matter
   pch.quizShowAnswer

   B — Exactly 1,225 comparisons -- n(n-1)/2 -- and recursion depth 49 — Measured exactly, at n = 10, 20 and 50: 45, 190 and 1,225, matching n(n-1)/2 precisely. Every partition peels off one element. With a randomised pivot the same input took ~245 comparisons and depth ~9. In Python the depth is the more urgent problem -- n-1 frames hits CPython's ~1,000 limit long before the time does.

3. Sorting [(1,'a'), (1,'b'), (0,'c')] by the first element, quicksort returns [(0,'c'), (1,'b'), (1,'a')]. Is that a bug?

   A Yes -- the keys are out of order B No -- it is correctly sorted by key, but quicksort is not stable, so equal elements can be reordered C Yes -- the pivot choice was wrong D No, and sorted() would give the same result
   pch.quizShowAnswer

   B — No -- it is correctly sorted by key, but quicksort is not stable, so equal elements can be reordered — The keys read 0, 1, 1 -- correct. What changed is the relative order of the two equal keys, which `sorted` preserves and quicksort does not. Long-range swaps are what make quicksort fast and are exactly what breaks stability: an element can jump past an equal element it never compared against.

4. Why does the partition test use `arr[j] <= pivot` rather than `<`?

   A It makes no difference B With `<`, values equal to the pivot all land on the right, so an all-equal array gives maximally unbalanced splits -- O(n^2) C `<` would skip the pivot itself D `<=` is required for stability
   pch.quizShowAnswer

   B — With `<`, values equal to the pivot all land on the right, so an all-equal array gives maximally unbalanced splits -- O(n^2) — On [5, 5, 5, ..., 5] with strict `<`, no element ever satisfies the test, so every partition peels off exactly one element -- the quadratic case, triggered by an input that looks trivially easy. Neither operator gives stability. When duplicates are common the real fix is a three-way Dutch-flag partition, which finishes an all-equal array in one pass.

5. You switch to Hoare's partition scheme. What must change in the recursion?

   A Nothing -- both return the pivot's final index B Hoare returns a split point, not the pivot's position, so the calls become go(low, p) and go(p+1, high) rather than p-1/p+1 C You must sort each half twice D Hoare requires the array to be shuffled first
   pch.quizShowAnswer

   B — Hoare returns a split point, not the pivot's position, so the calls become go(low, p) and go(p+1, high) rather than p-1/p+1 — This is the reason textbooks teach Lomuto: its return value is the pivot's final resting place, so excluding it with p-1/p+1 is natural. Hoare's index only says "everything left is <= everything right" -- exclude it and you drop an element; use Lomuto's convention with Hoare's partition and you can recurse forever. Hoare does roughly 3x fewer swaps, which is why production implementations prefer it.

6. What is quicksort's space complexity?

   A O(1) -- it sorts in place B O(log n) expected and O(n) worst case, because the recursion stack is the space C O(n) always D O(n log n)
   pch.quizShowAnswer

   B — O(log n) expected and O(n) worst case, because the recursion stack is the space — In-place refers to the data movement, not the call stack. Balanced splits give log n frames; the degenerate case gives n, which is measurable -- depth 49 for a sorted 50-element array. Recursing into the smaller side and looping on the larger bounds it at O(log n) even on bad splits, and is worth mentioning as the fix.

Recall card

• Quicksort = partition, then recurse on both sides. Interviews ask for the partition, not the sort.
• Lomuto: pivot is the last element, i tracks the $\le$ boundary, j scans, final swap puts the pivot at i + 1 — its permanent position.
• Partitioning sorts nothing. It places one element and splits the rest. [8,3,1,7,0,2] becomes [1,0,2,7,3,8]; only index 2 is final.
• Test with <=, not < — strict comparison sends all equal values right, making [5]*n the quadratic case.
• Randomise the pivot. Sorted input with a fixed pivot costs exactly $n(n-1)/2$ comparisons and depth n-1: 1,225 and 49 at n = 50, against ~245 and ~9 randomised.
• In Python the depth is the danger — n-1 frames hits the ~1,000-frame limit as a RecursionError.
• Space is $O(\log n)$ expected, $O(n)$ worst case (the stack). Recurse into the smaller side and loop on the larger to bound it.
• Not stable. [(1,'a'),(1,'b'),(0,'c')] comes back with a and b swapped. Long-range swaps are the cause.
• Hoare returns a split point, not the pivot’s index — recurse (low, p) and (p+1, high). ~3x fewer swaps; used in production.
• Many duplicates -> three-way (Dutch flag) partition, which finishes an all-equal array in one pass.

Interview follow-ups

They ask	What they’re checking	The answer
“Sort this array” (in Python)	Judgement	list.sort() — Timsort in C. Then offer to implement quicksort if the point is the algorithm. Hand-writing a sort in Python when the stdlib exists is the wrong instinct to display
“What is the worst case, and when does it happen?”	Whether you know the trigger	$O(n^2)$, on already-sorted (or reverse-sorted) input with a fixed end pivot, and on all-equal input with a strict < test. Measured: exactly $n(n-1)/2$ comparisons and depth n-1
“Fix the worst case”	Ranking the fixes	Randomise the pivot (one line, makes it unlikely), or introsort — switch to heap sort past a depth limit, which makes it impossible. Median-of-three is cheap and defeats sorted input specifically
“Space complexity?”	In-place is not $O(1)$	$O(\log n)$ expected, $O(n)$ worst case — the recursion stack. Recurse into the smaller partition and loop on the larger to bound it at $O(\log n)$ regardless
“Is it stable? Does that matter here?”	Whether you check the requirement	Not stable — verified, [(1,'a'),(1,'b'),(0,'c')] returns a and b swapped. It matters whenever a previous ordering must survive; then use merge sort or sorted
“The array is all duplicates”	The <=/< trap	With strict < every partition peels one element: $O(n^2)$ on an input that looks trivial. Three-way Dutch-flag partitioning finishes it in a single pass
“Now give me the kth largest”	The real interview question	Quickselect: partition once, compare the pivot index with n - k, recurse on one side. $O(n)$ expected, $O(1)$ space
“Why does quicksort beat merge sort in practice despite the worse worst case?”	Constant factors	In-place partitioning is sequential and cache-friendly, with no allocation; merge sort allocates and copies. Same asymptotic class, very different constant
“How deep can the recursion go in Python?”	Practical limits	n - 1 in the worst case, and CPython dies at ~1,000 frames — so an adversarial 10,000-element input is a RecursionError, not a slow sort

Recap

• Quicksort = partition around a pivot, then recurse on both sides — no merge step needed.
• The Lomuto scheme picks the last element as pivot and tracks a growing ”$\le$ pivot” region with index i; Hoare’s two-pointer scheme does fewer swaps but returns a split point, not the pivot’s final index.
• Fixed pivot choice (always last element) degrades to $O(n^2)$ on sorted or reverse-sorted input — the exact input you’d expect to see often.
• A randomized (or median-of-three) pivot makes that worst case practically unreachable, restoring the expected $O(n \log n)$.
• In-place, $O(\log n)$ average extra space, not stable.

Next: Heap Sort — a comparison sort with a guaranteed $O(n \log n)$ worst case, no randomization required, built directly on the binary heap from Phase 3.