Pick a kid, split the room
Quick Sort
The analogy
Point at one kid — the pivot. Everyone shorter shuffles to their left, everyone taller to their right. That pivot is now in their final spot forever, and you repeat on each side. Fast when your pivot lands near the middle; slow if you keep picking the tallest.
Visualizer
Watch the room split
step 1 / 335
3
8
1
9
2
7
4
8 numbers, out of order. Press play — or step through one comparison at a time.
📖 In depth — the full reference
The sorting scoreboard (for reference across all five sorting lessons)
| algorithm | best | average | worst | extra space | stable? |
|---|---|---|---|---|---|
| bubble | O(n) with early exit | O(n²) | O(n²) | O(1) | yes |
| selection | O(n²) — always | O(n²) | O(n²) | O(1) | no (long-range swaps) |
| insertion | O(n) on sorted input | O(n²) | O(n²) | O(1) | yes |
| merge | O(n log n) | O(n log n) | O(n log n) | O(n) | yes |
| quick | O(n log n) | O(n log n) | O(n²) (bad pivots) | O(log n) stack | no (typical) |
| Timsort (stdlib) | O(n) | O(n log n) | O(n log n) | O(n) | yes |
Quick sort — everything worth knowing
- Strategy inverted from merge sort: do the work BEFORE recursing (partition around a pivot), then the halves need no merging — the array is sorted when the recursion bottoms out.
- Average O(n log n) with constants small enough to beat merge sort in RAM; in-place (O(log n) stack only), which is why C's qsort and C++'s introsort build on it.
- The O(n²) horror story: always picking the smallest/largest pivot (e.g. first element of SORTED input) makes one side empty — n levels × n work. Fixes: random pivot, median-of-three, or introsort's escape hatch (switch to heapsort past 2·log n depth).
- Partition schemes: Lomuto (single scan, simpler, more swaps) vs Hoare (two converging pointers, fewer swaps). Your exercise's two-bucket pass is the readable out-of-place version.
- Not stable in its fast in-place form — equal elements can leap across the pivot.
- Quickselect: recurse into ONE side only to find the k-th smallest in O(n) average — the median-finding trick interviews love.
Python corner
import random
# random.choice as pivot defuses the sorted-input bomb
def quicksort(xs):
if len(xs) <= 1: return xs
p = random.choice(xs)
return (quicksort([x for x in xs if x < p])
+ [x for x in xs if x == p]
+ quicksort([x for x in xs if x > p]))
# Readable, correct, O(n) extra memory. Python itself still uses
# Timsort — this is for understanding, and for interviews.def quick_sort(a, lo=0, hi=None):
hi = len(a) - 1 if hi is None else hi
if lo >= hi:
return a
p = partition(a, lo, hi)
quick_sort(a, lo, p - 1)
quick_sort(a, p + 1, hi)
return a
def partition(a, lo, hi):
pivot, i = a[hi], lo
for j in range(lo, hi):
if a[j] < pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
return iCheck yourself
After one partition, what is guaranteed?
Practice — write it yourself
The heart of quicksort: partition(arr, pivot) returns [smaller, equal_or_larger] — two lists, one pass, order preserved within each side.
Python 3 · runs in your browser · your draft is saved locally
📝 My notessaved in this browser