Quick Sort in Three Lines, and Why It's Wrong
Every interview blog shows the cute three-line quicksort. It's a teaching aid that looks elegant and ships bugs: O(n log n) extra memory, quadratic on sorted input, and unstable. Here is the cute version, the in-place version we should actually write, and the version with a randomized pivot.
By @nathanmurphy
February 13, 2026
·
Updated August 19, 2026
480 views
4
Rate
from __future__ import annotations
# The version that fits in a tweet. Looks like Haskell. Hides three problems:
# 1. O(n log n) extra memory: every recursion allocates two new lists.
# 2. O(n^2) on sorted/reverse-sorted input because xs[0] is always the worst pivot.
# 3. Unstable: equal elements can be reordered relative to their input order.
def quicksort_cute(xs):
if len(xs) <= 1:
return xs
pivot = xs[0]
less = [x for x in xs[1:] if x < pivot]
equal = [x for x in xs if x == pivot]
greater = [x for x in xs[1:] if x > pivot]
return quicksort_cute(less) + equal + quicksort_cute(greater)
import random
random.seed(0)
random_input = [random.randint(0, 100) for _ in range(20)]
sorted_input = list(range(20))
print('random ->', quicksort_cute(random_input))
print('sorted ->', quicksort_cute(sorted_input))
# Show the worst-case behavior: depth on already-sorted input.
import sys
sys.setrecursionlimit(50)
longest = list(range(40))
try:
quicksort_cute(longest)
print('40 sorted: completed')
except RecursionError as e:
print('40 sorted: RecursionError (worst-case depth)')The three-line version is real code I have seen in code reviews and even in shipping production scripts. It is a useful teaching aid because the recursion structure is unusually visible, but every list comprehension allocates a fresh list, doubling the asymptotic memory. The bigger problem is the pivot choice: xs[0] on already-sorted input puts every element into greater and the recursion depth becomes O(n), which on a 10k-element sorted list will overflow Python's default recursion limit. The third problem (instability) only matters when sorting tuples by one field while preserving the order of another, but it is the same root cause: equal elements get hoisted into the equal bucket out of input order.
from __future__ import annotations
# Lomuto partition: pick a pivot, walk i from lo to hi-1, keep an index 'store'
# that marks the boundary between 'known < pivot' and 'unknown'. Swap as we go.
# O(n) per partition, O(1) extra memory, in-place. The recursion depth is the
# only memory cost, and with median-of-three pivot it stays around log n.
def quicksort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo >= hi:
return
p = partition(arr, lo, hi)
quicksort(arr, lo, p - 1)
quicksort(arr, p + 1, hi)
def partition(arr, lo, hi):
# Median-of-three: pick the median of arr[lo], arr[mid], arr[hi] as pivot.
# This is the cheapest defense against sorted/adversarial input.
mid = (lo + hi) // 2
a, b, c = arr[lo], arr[mid], arr[hi]
# Sort the three and put the median at hi.
if a > b: arr[lo], arr[mid] = arr[mid], arr[lo]
if arr[lo] > arr[hi]: arr[lo], arr[hi] = arr[hi], arr[lo]
if arr[mid] > arr[hi]: arr[mid], arr[hi] = arr[hi], arr[mid]
pivot = arr[hi]
store = lo
for i in range(lo, hi):
if arr[i] < pivot:
arr[store], arr[i] = arr[i], arr[store]
store += 1
arr[store], arr[hi] = arr[hi], arr[store]
return store
import random
random.seed(0)
a = [random.randint(0, 100) for _ in range(15)]
print('before:', a)
quicksort(a)
print('after :', a)
# Sorted input no longer blows the stack thanks to median-of-three.
b = list(range(40))
quicksort(b)
print('sorted input handled, first/last:', b[0], b[-1])The in-place version is what I would write in an interview if asked for quicksort. The partition step is the standard Lomuto scheme; the median-of-three pivot is the smallest defense against the worst case that a real implementation needs. Without it, sorted or reverse-sorted input still degrades to O(n^2) and overflows the stack on inputs around 1000 elements (Python's default recursion limit). Lomuto is easier to memorize and teach than Hoare partition; for production-grade speed you would prefer Hoare and dual-pivot, but for clarity and correctness Lomuto is the right interview answer.
from __future__ import annotations
import random
# When the input distribution is adversarial (or just unknown), randomizing
# the pivot at each partition is the cleanest way to get expected O(n log n)
# regardless of input shape. The downside is non-determinism in tests; the
# upside is no input pattern can hit the worst case.
def quicksort(arr, lo=0, hi=None, rng=None):
if hi is None:
hi = len(arr) - 1
if rng is None:
rng = random.Random(0) # seeded so this snippet's output is reproducible
if lo >= hi:
return
p = partition(arr, lo, hi, rng)
quicksort(arr, lo, p - 1, rng)
quicksort(arr, p + 1, hi, rng)
def partition(arr, lo, hi, rng):
# Random pivot: swap a random element into the hi slot, then run Lomuto.
pivot_idx = rng.randint(lo, hi)
arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
pivot = arr[hi]
store = lo
for i in range(lo, hi):
if arr[i] < pivot:
arr[store], arr[i] = arr[i], arr[store]
store += 1
arr[store], arr[hi] = arr[hi], arr[store]
return store
# Even on adversarial input (sorted, all-equal, reverse-sorted) the
# randomized version stays balanced in expectation.
for name, data in [
('sorted ', list(range(20))),
('reversed ', list(range(20, 0, -1))),
('all-equal ', [7] * 20),
('random ', [random.Random(1).randint(0, 100) for _ in range(20)]),
]:
a = list(data)
quicksort(a)
print(name, '->', a)Randomized pivot is the version I reach for whenever the input distribution is unknown, which in production is most of the time. Picking a random index in [lo, hi] and swapping it into the hi slot lets us reuse the same Lomuto partition as the previous accordion; the only change is two extra lines. The threading of rng through the recursion is the part most three-line versions skip, and it matters because using random.random() means the sort is not reproducible across runs, which makes test failures hard to investigate. Seeding the rng at the top of the call gives both reproducibility and balanced expected partitions. For all-equal arrays the randomization buys you nothing (Lomuto is O(n^2) on duplicates regardless), and for that case three-way Dutch-flag partition is the right next step.