Merge sort (04-03) gave us the Θ(n log n) guarantee... at the price of O(n) memory. Quicksort attacks the same question with the same parent strategy — divide and conquer (03-01) — but inverting where the effort lives: in merge sort dividing is a dumb cut and all the work is in combining; in quicksort all the work is in dividing (the partition around a pivot) and combining is literally doing nothing. That inversion gives it what merge sort lacked — it sorts in-place, without linear auxiliary memory — in exchange for the risk we have been announcing since 02-03: an excellent O(n log n) average case living alongside an O(n²) worst case that you must know how to tame. In this lesson we will build the Lomuto partition step by step, trace it over the RutaBus arrivals, collect on the promised case analysis, and close with the comparison table of the course's three sorting algorithms.
Contents
- The inverted idea: the work happens when dividing
- The Lomuto partition, step by step
- Trace of the partition over the RutaBus board
- Complete recursive implementation
- Case analysis: the promise from 02-03, collected
- Taming the worst case: randomized pivot and median-of-three
- Stability, space, and the final table of the three sorts
The inverted idea: the work happens when dividing
Quicksort's plan for sorting a segment of the list:
- Divide (all the work is here): choose an element as the pivot and rearrange the segment so it becomes [less than or equal to the pivot] + [pivot] + [greater]. This rearrangement is called the partition and it leaves the pivot in its final, definitive position.
- Conquer: recursively sort the left block and the right block.
- Combine: nothing. Zero. If the left ends up sorted, the pivot is in its place and the right ends up sorted, the list is already sorted — the blocks never touch each other.
Compare it with merge sort, its mirror sibling:
| Merge sort | Quicksort | |
|---|---|---|
| Divide | Trivial: cut through the center | All the work: the partition |
| Combine | All the work: merge |
Trivial: nothing to do |
| Guaranteed halves? | Yes, always n/2 and n/2 | No: depends on the pivot |
That last row is the source of all of quicksort's glory and all of its misery. Merge sort cuts through the center by construction; quicksort cuts wherever the pivot happens to land. If the pivot turns out to be middling, perfect halves; if it turns out to be the minimum or the maximum, one "half" is empty and the other holds almost everything — and there begins the drama of section 5.
The Lomuto partition, step by step
There are several partition schemes; Lomuto's is the easiest to reason about. It works on the segment items[left..right], takes the last element as the pivot, and maintains a boundary i that separates what has already been classified as "≤ pivot" from the rest:
def partition(items, left, right):
pivot = items[right] # pivot: the last element of the segment
i = left - 1 # boundary: last index of the "≤ pivot" zone
for j in range(left, right): # j sweeps the whole segment except the pivot
if items[j] <= pivot:
i += 1 # grow the smaller zone...
items[i], items[j] = items[j], items[i] # ...and bring the element into it
items[i + 1], items[right] = items[right], items[i + 1] # pivot to its final place
return i + 1 # final position of the pivotThe loop invariant (our tool from 04-01) is a snapshot in three zones: at all times, items[left..i] holds elements ≤ pivot, items[i+1..j−1] holds elements > pivot, and from j onward lies the pending part. Each round examines items[j]:
- If it is > pivot: nothing to do — it is already attached to the greater zone.
- If it is ≤ pivot: it is swapped with the first element of the greater zone (
items[i+1]), so both zones grow by one position while keeping the invariant.
When the loop ends, the final swap plants the pivot between the two zones: everything to its left is ≤ and everything to its right is >. The pivot will never move again.
Trace of the partition over the RutaBus board
Let's partition the full L1 arrivals board (segment 0..4, pivot = "18:31", the last element):
j |
items[j] |
≤ "18:31"? |
Action | State (boundary i after the action) |
|---|---|---|---|---|
| — | — | — | initial, i = −1 |
[18:42, 18:07, 18:59, 18:12, 18:31] |
| 0 | 18:42 |
no | nothing | [18:42, 18:07, 18:59, 18:12, 18:31], i = −1 |
| 1 | 18:07 |
yes | i=0; swap positions 0↔1 |
[18:07, 18:42, 18:59, 18:12, 18:31], i = 0 |
| 2 | 18:59 |
no | nothing | [18:07, 18:42, 18:59, 18:12, 18:31], i = 0 |
| 3 | 18:12 |
yes | i=1; swap positions 1↔3 |
[18:07, 18:12, 18:59, 18:42, 18:31], i = 1 |
| end | — | — | pivot to position i+1=2: swap 2↔4 |
[18:07, 18:12, 18:31, 18:42, 18:59] |
The function returns 2: the pivot "18:31" has landed at index 2, its final position in the sorted list — you can check it: it is the median of the five times. To its left, {18:07, 18:12} (unsorted with respect to each other, no matter: they are already "the right ones"); to its right, {18:42, 18:59}. Each half will be handled by a recursive call, and in this example both are segments of 2 that one more partition leaves finished.
Cost of one partition: the loop sweeps the segment once — O(n) in the size of the segment, with swaps inside the list itself.
Complete recursive implementation
def quicksort(items, left=0, right=None):
"""Sorts items[left..right] in place."""
if right is None:
right = len(items) - 1
if left >= right: # base case: 0 or 1 elements
return
p = partition(items, left, right) # DIVIDE: pivot placed at p
quicksort(items, left, p - 1) # CONQUER left half
quicksort(items, p + 1, right) # CONQUER right half
# COMBINE: nothing to doDetails:
- It works on the list itself with
left/rightindices, without creating sublists — unlike the copying cuts ofmerge_sort. That is why it is in-place. - The recursive calls exclude
p: the pivot is already placed forever. Including it (quicksort(items, left, p)) causes infinite recursion as soon as a segment fails to shrink. - The base case
left >= rightcovers segments of 1 element and also empty ones (left > right), which appear when the pivot lands at an extreme.
board = ["18:42", "18:07", "18:59", "18:12", "18:31"]
quicksort(board)
print(board) # ['18:07', '18:12', '18:31', '18:42', '18:59']Case analysis: the promise from 02-03, collected
In 02-03 we announced quicksort as "the celebrated example" of the average/worst-case gap. Let's collect on the promise. The total cost is the sum of all the partitions, and how much they add up to depends on where the pivots land:
Best case — Θ(n log n): middling pivots. If each pivot splits its segment into two ≈ equal halves, the call tree is merge sort's: log₂ n levels, and the partitions at each level add up to O(n) between them (they sweep disjoint segments that cover the list). Total: the recurrence T(n) = 2·T(n/2) + O(n) we solved in 04-03 → Θ(n log n).
Worst case — Θ(n²): extreme pivots. If each pivot turns out to be the maximum (or minimum) of its segment, the partition leaves one block of n−1 and one empty. The recurrence degenerates into T(n) = T(n−1) + O(n): partitions of n, n−1, n−2, ... — the arithmetic sum n(n−1)/2 from 02-01 → Θ(n²). And here comes the cruel irony: with Lomuto's pivot (the last element), this catastrophe is triggered by... an already sorted list (or a reversed one). Each pivot is the maximum of its segment, and the "quick" sort crawls to n²: exactly the input on which humble insertion sort (04-02) ran in Θ(n). On top of that, the recursion piles up n levels: with our board of 10,000 already sorted arrivals, Python blows through the stack limit (RecursionError, remember 02-02) before it even finishes being slow.
Average case — Θ(n log n): the statistical reality. With inputs in random order (a distribution that must be declared, 02-03), the pivot is rarely extreme. It does not need to be the median: it is enough for it to land "around the middle" reasonably often. Even a pivot that only guarantees a 10%–90% split keeps the depth logarithmic (a log with a different base — a constant the notation absorbs, 01-03). The formal analysis gives ≈ 1.39·n·log₂ n expected comparisons: Θ(n log n) with a small constant. That small constant, plus the in-place work without copies (locality and no memory cost), is what makes quicksort beat merge sort in practice almost always... except on the day it doesn't.
| Case | Input that triggers it (Lomuto, last-element pivot) | Cost |
|---|---|---|
| Best | Always-middling pivots | Θ(n log n) |
| Average | Uniformly random order | Θ(n log n), ≈ 1.39·n·log₂ n |
| Worst | Already sorted, reversed or extreme pivots | Θ(n²) |
This is 02-03 applied: if your inputs are random and volume rules, the average represents you; if a user (or an attacker — the "hostile inputs" table from 02-03) can send you the pathological input, the worst case is your contract. A RutaBus endpoint that sorts whatever the client sends with this quicksort is a denial-of-service attack waiting to happen: sending already sorted lists is enough.
Taming the worst case: randomized pivot and median-of-three
The worst case cannot be eliminated, but it can be made improbable or impractical:
Randomized pivot. Before partitioning, swap the last element with one chosen at random:
import random
def partition_randomized(items, left, right):
r = random.randint(left, right) # random pivot from the segment
items[r], items[right] = items[right], items[r] # move it to the end...
return partition(items, left, right) # ...and partition as usualThis turns quicksort into a randomized algorithm (01-02): the cost no longer depends on the input but on the internal dice. No input is pathological in itself — not the sorted one, not the attacker's, who can no longer predict the pivots —; the worst case still exists (n extreme pivots could come up in a row) but its probability collapses exponentially. The expected cost is Θ(n log n) for every input.
Median-of-three. A deterministic, cheap alternative: use as the pivot the median of the first, middle and last elements of the segment. It stone-cold neutralizes the "already sorted / reversed" cases (the median-of-three of a sorted list is the central element: a perfect partition) and improves the constants in practice, although an adversary who knows the rule can still construct bad inputs — which is why serious libraries combine tricks or switch algorithms if they detect the recursion sinking too deep (the so-called introsorts).
Stability, space, and the final table of the three sorts
It is not stable. The partition's swaps leap over whole stretches and can invert ties. With the tuple board from 04-02, [("18:30", "L2"), ("18:05", "L1"), ("18:30", "L1")] and pivot ("18:30", "L1"): the partition places the pivot ahead of the ("18:30", "L2") that originally preceded it — tie inverted. If you need to sort by time while preserving the order by line, quicksort is not your tool (merge sort or Timsort is).
Space: in-place, with a caveat. The partition uses no auxiliary memory — unlike merge sort's O(n) (02-02), there are no new lists here. The only expense is the recursion stack: O(log n) frames when the partitions are balanced, but O(n) in the worst case — one more reason to tame the pivots.
The table that sums up three lessons of sorting:
| Insertion sort (04-02) | Merge sort (04-03) | Quicksort (04-04) | |
|---|---|---|---|
| Best case | Θ(n) | Θ(n log n) | Θ(n log n) |
| Average case | Θ(n²) | Θ(n log n) | Θ(n log n) (small constant) |
| Worst case | Θ(n²) | Θ(n log n) guaranteed | Θ(n²) (mitigable) |
| Auxiliary space | O(1) | O(n) | O(log n) expected (stack) |
| Stable? | Yes | Yes | No |
| In-place? | Yes | No | Yes |
| Choose it for... | Small segments, nearly sorted, online | Hard guarantees, stability, external data | General in-memory use: the fastest in practice |
No column dominates the others: it is a menu of trade-offs, not a podium. Real libraries confirm it by composing: Timsort (Python) = merge + insertion; C++'s introsorts = quick + heap + insertion.
Common Mistakes and Tips
- Including the pivot in the recursive calls (
quicksort(items, left, p)): if a segment fails to shrink, infinite recursion. The pivot is placed: it is always excluded (p − 1andp + 1). - Forgetting that the already sorted list is Lomuto's worst case. It is counterintuitive (the "easy" input!) and very common in production, because real data often arrives nearly sorted. If you use a fixed pivot, your benchmark on random data will lie about your production. Randomized pivot or median-of-three, always.
- Many duplicates degrade Lomuto: if the board has thousands of arrivals with the same time, all the "≤ pivot" elements fall on the same side and the partitions come out unbalanced even with a reasonable pivot. The classic solution is the three-way partition (<, =, >), which groups the elements equal to the pivot and never touches them again.
- Assuming stability: quicksort sorts fine, so the mistake shows no symptoms until a tie matters (and then it is a "random" bug that is hard to reproduce). When keys have meaningful ties, merge/Timsort.
- Tip: in real Python,
sorted()/list.sort()(Timsort) beat any homemade quicksort — implementing it here is about understanding the mechanism and its trade-offs, which reappear as-is in the C, C++, Java or Rust libraries that do use it.
Exercises
Exercise 1
Trace the Lomuto partition (a table like the one in section 3) over ["18:20", "18:55", "18:04", "18:47", "18:33"] (pivot "18:33"). State the position returned and which two subsegments will be sorted recursively.
Exercise 2
Without running code: how many comparisons does this quicksort (Lomuto, last-element pivot) make on the already sorted board ["18:01", "18:02", "18:03", "18:04", "18:05"]? List the pivot of each call and generalize the count to n. Which algorithm from this module would have made only n−1 comparisons on this input?
Exercise 3
The RutaBus app needs the 10 earliest arrivals out of a listing of n = 100,000, and someone winces at sorting the whole thing. Building on the partition: write k_earliest(items, k) that uses the quicksort idea but recurses only into the side where the answer lies (this algorithm is called quickselect). Reason about why its average cost is O(n) and not O(n log n). Hint: it is the "counting halves" argument from 04-01, but summing instead of counting.
Solutions
Solution 1
Pivot "18:33", i = −1:
j |
items[j] |
≤ 18:33? |
Action | State |
|---|---|---|---|---|
| 0 | 18:20 |
yes | i=0; swap 0↔0 (stays the same) |
[18:20, 18:55, 18:04, 18:47, 18:33] |
| 1 | 18:55 |
no | nothing | unchanged |
| 2 | 18:04 |
yes | i=1; swap 1↔2 |
[18:20, 18:04, 18:55, 18:47, 18:33] |
| 3 | 18:47 |
no | nothing | unchanged |
| end | — | — | pivot to position 2: swap 2↔4 | [18:20, 18:04, 18:33, 18:47, 18:55] |
It returns 2. Recursive subsegments: [18:20, 18:04] (indices 0–1) and [18:47, 18:55] (indices 3–4). Note the "swap with itself" at j = 0: harmless and normal in Lomuto.
Solution 2
With the list sorted, each pivot (the last element) is the maximum of its segment: the partition compares the whole segment, leaves the pivot where it was, and recurses on a segment with one element fewer. Successive pivots: 18:05, 18:04, 18:03, 18:02. Comparisons: 4 + 3 + 2 + 1 = 10. In general: (n−1) + (n−2) + ... + 1 = n(n−1)/2 — the arithmetic sum, Θ(n²). Insertion sort (04-02) would have made n−1 = 4 comparisons: its best case is exactly this quicksort's worst.
Solution 3
import random
def quickselect(items, left, right, k):
"""Places at items[k] the element that would sit there in the sorted list."""
if left >= right:
return
r = random.randint(left, right)
items[r], items[right] = items[right], items[r]
p = partition(items, left, right)
if k < p:
quickselect(items, left, p - 1, k) # the answer is on the left
elif k > p:
quickselect(items, p + 1, right, k) # ...or on the right: ONE side only
# if k == p, it is already in place
def k_earliest(items, k):
quickselect(items, 0, len(items) - 1, k - 1)
return sorted(items[:k]) # k elements: sorting this is cheapAfter quickselect, the k−1 preceding positions contain (unordered) the smaller elements: items[:k] are exactly the k earliest. Average cost: each partition costs the size of the segment, but by recursing into one side only the expected segments halve: n + n/2 + n/4 + ... ≤ 2n → O(n). Compared with "counting halves" from 04-01: there the levels were counted (log n); here their costs are summed (geometric series → 2n). Sorting the whole thing would cost n log n ≈ 1.7 million operations; quickselect, ≈ 200,000.
Conclusion
Quicksort is merge sort's mirror image: same parent (divide and conquer), opposite effort — the Lomuto partition places the pivot in its definitive position in O(n) and leaves two independent subproblems, with nothing to combine. We have collected on the promise from 02-03: a Θ(n log n) average with a small constant that makes it the fastest in practice, a Θ(n²) worst case that — irony — is triggered by the already sorted input with a naive pivot, and the two vaccines: a randomized pivot (a randomized algorithm of the 01-02 kind, expected cost n log n for every input) and median-of-three. It is not stable, but it is in-place — the space advantage merge sort lacked — and the final insertion/merge/quick table shows that choosing a sort means choosing trade-offs, not champions. With lists mastered, we change structure: the RutaBus stop network we modeled as a graph in 03-04 awaits us with the most useful question in the whole app — what is the shortest path between two stops? — and with the algorithm we announced in 03-02 as "the greedy that is optimal": Dijkstra.