What you'll learn
Quick sort is the sorting algorithm most standard libraries reach for. It sorts in place and averages O(n log n) with small constants — usually beating merge sort in practice. The trick is partitioning around a pivot.
By the end you'll be able to:
- Partition an array around a pivot
- Trace quick sort's recursive calls
- Explain its
O(n²)worst case and how pivot choice avoids it
The partition idea
Pick a pivot element. Rearrange the array so everything smaller than the pivot is to its left and everything larger is to its right — the pivot is now in its final sorted position. Then recurse on the left and right parts. No merge step and no extra array needed.
This animation uses Lomuto partitioning: the last element is the pivot, pointer j scans, and i marks the boundary of the "smaller" region.
Watch it sort
In code
def quick_sort(a, lo=0, hi=None):
if hi is None:
hi = len(a) - 1
if lo >= hi:
return a
p = partition(a, lo, hi)
quick_sort(a, lo, p - 1) # left of pivot
quick_sort(a, p + 1, hi) # right of pivot
return a
def partition(a, lo, hi):
pivot = a[hi] # Lomuto: last element
i = 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] # pivot into place
return iPivots & the worst case
Quick sort's speed depends entirely on the pivot splitting the array evenly. If the pivot is always the smallest or largest element (for example, picking the last element of an already sorted array), one side is empty and the recursion depth becomes n — degrading to O(n²).
Watch out
O(n log n).Complexity
| Case | Time | When |
|---|---|---|
Best / Average | O(n log n) | Pivot splits the array roughly in half |
Worst | O(n²) | Pivot is always the min or max (e.g. sorted input, last-element pivot) |
Space | O(log n) | Recursion stack (in-place partition) |
Stable? | No | Swaps can reorder equal elements |
Recap & quick check
Key takeaways
- Quick sort partitions around a pivot: smaller left, larger right, pivot in its final place.
- It recurses on the two sides — no merge step and no extra array (in-place).
- Average is O(n log n) with small constants; it's usually the fastest general sort.
- Worst case is O(n²) when pivots split badly (e.g. sorted input with a naive pivot).
- Random or median-of-three pivots make the worst case very unlikely.
Quick check
1. After one partition step, the pivot is:
2. Quick sort's average time complexity is:
3. What causes quick sort's O(n²) worst case?
4. A common way to avoid the worst case is:
Merge and quick sort are the workhorses. Next: sorting with a heap, and breaking O(n log n) entirely. Next up: Module 13 — Heap Sort & Linear-Time Sorts.