Quick sort is the fast, in-place sort you will meet most often in practice. Its whole trick lives in one step called partition: pick a value (the pivot), then shuffle the array so everything smaller ends up on its left and everything bigger on its right. After that, the pivot is in its final spot — and you repeat on each side.
Step through the animation on the right. Watch j scan the array, the boundary i creep forward, and the pivot finally drop into the one slot where it belongs. The highlighted code line shows exactly what is happening at each scan and swap.
The idea
Partition splits the array around a pivot. We use the Lomuto scheme: the pivot is the last element, and we keep a boundary i that marks the end of the "smaller than pivot" zone. A scanner j walks across the rest. Every time a[j] is smaller than the pivot, we grow the small zone by one and swap that value in.
When the scan finishes, everything left of i+1 is smaller than the pivot and everything right is bigger. So we swap the pivot into slot i+1 — and it is now in its final, sorted position. Quick sort then calls itself on the left side and the right side.
Walk through it
Press Play on the right, or step with Next / Back. The array is [7, 2, 9, 3, 5] and the pivot is 5 (the last cell). Notice:
j(above) scans left to right. The cell it is checking turns blue.- When
a[j] < 5, the boundaryimoves forward and two cells turn red and slide — that is the swap. 7and9are not smaller than5, so they get skipped.2and3are smaller, so they get pulled left.- At the end, the pivot
5swaps into slot2and turns green. Smaller values (2, 3) sit on its left, bigger (7, 9) on its right.
The pivot lands at index 2 — its permanent home. Each side is then sorted the same way.
The code, line by line
def partition(a, lo, hi):
pivot = a[hi] # last element
i = lo - 1 # boundary
for j in range(lo, hi):
if a[j] < pivot:
i += 1
a[i], a[j] = a[j], a[i]
a[i + 1], a[hi] = a[hi], a[i + 1]
return i + 1
def quick_sort(a, lo, hi):
if lo < hi:
p = partition(a, lo, hi)
quick_sort(a, lo, p - 1)
quick_sort(a, p + 1, hi)pivot = a[hi]picks the last element as the pivot.i = lo - 1starts the boundary just left of the range — the "smaller" zone is empty.- The
for jloop scans every element before the pivot. if a[j] < pivotis the comparison you see in blue. When it is true, we bumpiforward and swapa[i]witha[j]— that grows the small zone.- After the loop,
a[i+1], a[hi] = ...swaps the pivot into the gap right after the small zone. That index is its final home, sopartitionreturnsi + 1. quick_sortthen recurses on the left part (lo..p-1) and the right part (p+1..hi). The pivot itself is already done.
Complexity
| Case | Time | Notes |
|---|---|---|
| Best | O(n log n) (moderate) | pivot splits the array roughly in half each time |
| Average | O(n log n) (moderate) | random data balances the splits |
| Worst | O(n²) (slow) | pivot is always the smallest or largest (e.g. sorted input) |
O(log n) (fast)Each partition does O(n) work. If the pivot splits the array evenly, there are about log n levels of recursion — so n × log n total. The worst case is a bad pivot every time (like an already-sorted array with the last-element rule): one side is empty, so you get n levels of O(n) work, which is O(n²). The O(log n) space is the recursion stack.
When to use / pitfalls
Quick sort is usually the fastest general-purpose sort in practice — it is in-place and cache-friendly.
The catch is the O(n²) worst case. Real libraries dodge it by choosing the pivot smartly: pick a
random element, or the median of the first, middle, and last. In an interview, be ready to explain the
partition step and why a good pivot keeps the splits balanced.
Two common bugs. First, quick sort is not stable — equal values can swap order, so do not use it
when stability matters. Second, always-picking the last element as the pivot makes sorted input the
worst case (O(n²)); randomize or use median-of-three to avoid it.
Practice
After one partition of [7, 2, 9, 3, 5] with pivot 5, which value is guaranteed to be in its final sorted position, and at what index?
1. What does one partition step guarantee?
2. In the Lomuto scheme, when do we advance i and swap?
3. Why is quick sort O(n²) in the worst case?
4. How do real implementations avoid quick sort's worst case?