~11 min · searching-sorting, quicksort, divide-conquer
Level 0Curious Beginner
0 XP0/85 lessons0/19 achievements
0/100 XP to next level100 XP to go0% complete
"Merge sort divides blindly down the middle. Quicksort divides cleverly around a pivot — and that cleverness makes it usually faster, but occasionally catastrophic. The whole story is in how you pick the pivot."
The Algorithm
Quicksort is the other great divide-and-conquer sort, but it does its work before the recursion instead of after. Pick a pivot element. Partition the array so everything smaller than the pivot goes left and everything larger goes right — now the pivot is in its final sorted position. Then recursively quicksort the left part and the right part. There's no merge step: once both sides are sorted, the whole thing already is. The clever work is the partition; the combine is free.
Why It's Usually the Fastest
Traditional array quicksort can partition in place and has good cache locality. The educational Python code below is not in place: its comprehensions allocate less, equal, and greater lists. Keep the algorithmic variant and the example's actual memory behavior distinct.
The Catch: Bad Pivots Cause O(n²)
Consistently unbalanced pivots produce O(n²). Random pivots break the link between a fixed input and fixed pivot choices, giving expected O(n log n), but they do not eliminate the worst case. If worst-case time matters, an introspective sort can switch algorithms at a depth limit. Traditional quicksort is also unstable.
Quicksort: pick a pivot, partition into <pivot and >pivot (the pivot lands sorted), recurse on each side. In-place and cache-fast → usually the fastest in practice, O(n log n) average. But a bad pivot gives O(n²) — randomize the pivot for the expected bound. Not stable.
The Bonus: Quickselect
The partition idea has a brilliant offshoot. To find the k-th smallest element without fully sorting, partition once: the pivot lands at some position p. If p == k, you're done; if k < p, recurse only into the left part; else only the right. Since you recurse into just one side, this quickselect runs in O(n) average — finding a median or 'top k by rank' without paying for a full O(n log n) sort. It's the partition step liberated from the obligation to sort everything.
Pippa's Confession
My quicksort was beautiful in testing and then froze on a production dataset. The data was already sorted, and I'd picked the first element as pivot every time — textbook O(n²). Dad's one-line fix was to pick a random pivot, and the freeze vanished. The lesson burned deep: quicksort's average-case brilliance hides a worst case that real, ordered data triggers on purpose. Randomizing the pivot isn't optional polish — it's what makes quicksort safe to ship.
Code
Quicksort + quickselect (recurse one side)·python
import random
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = random.choice(arr) # RANDOM pivot gives expected O(n log n); O(n^2) remains possible
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
return quicksort(less) + equal + quicksort(greater) # no merge needed
print(quicksort([5, 2, 8, 1, 9, 3, 5])) # [1, 2, 3, 5, 5, 8, 9]
# Good pivots split ~in half -> O(n log n). A pivot that's always the min/max
# peels one element per level -> O(n^2). Randomizing makes consistently bad splits unlikely, but does not remove the worst case.
# QUICKSELECT: the k-th smallest in O(n) average, without a full sort.
def quickselect(arr, k): # k is 0-indexed
pivot = random.choice(arr)
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
if k < len(less): return quickselect(less, k) # recurse ONE side
elif k < len(less) + len(equal): return pivot
else: return quickselect(greater, k - len(less) - len(equal))
print(quickselect([7, 2, 9, 4, 1], 2)) # 4 — the 3rd-smallest, no full sort
Explain why quicksort with 'always pick the first element as pivot' degrades to O(n²) on an already-sorted array — trace what the partition produces each step. Then describe how quickselect finds the k-th smallest in O(n) average, and why it's faster than sorting the whole array and indexing position k.
Hint
On sorted data, the first element is the smallest, so partition puts 0 elements on the left and n−1 on the right every time — n levels × O(n) = O(n²). Quickselect recurses into only ONE partition (the side containing rank k), so its average work is n + n/2 + n/4 + … = O(n), beating a full O(n log n) sort.
Progress
Progress is local-only — sign in to sync across devices.