Quick sort picks a pivot, partitions the array so that everything smaller ends up on the left and everything larger on the right, then recurses on both halves. The pivot lands in its final sorted position after every partition, so the sorted region grows from scattered anchors inward rather than from one end.
Press play, or step through it one comparison at a time. Orange highlights the comparison against the pivot, yellow marks a swap, and green shows values that have reached their final position.
Ready. 12 values, unsorted.
0 comparisons · 0 swaps
Ready. 12 values, unsorted.
- Comparing
- Swapping
- Final position
Code
- def quick_sort(a, lo=0, hi=None):
- if hi is None:
- hi = len(a) - 1
- if lo >= hi:
- return a
- pivot = a[hi]
- i = lo - 1
- 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]
- p = i + 1
- quick_sort(a, lo, p - 1)
- quick_sort(a, p + 1, hi)
- return a
Try Worst case to watch the pivot land at the far end every time (O(n²)
comparisons), then Shuffle to see how random input gives a balanced split and
finishes in far fewer steps.
Time and space complexity
| Case | Complexity | Why |
|---|---|---|
| Best | O(n log n) | Each pivot lands near the middle, giving balanced partitions. |
| Average | O(n log n) | Random input produces roughly balanced splits on average. |
| Worst | O(n²) | Each pivot lands at the extreme end (e.g. already-sorted input with Lomuto). |
| Space | O(log n) | In-place partitioning. The stack depth is log n on average (O(n) worst case). |
| Stable | No | The partition swap can reorder equal values. |
The average case makes quick sort the fastest general-purpose comparison sort in practice. The O(n²) worst case is avoidable with randomised pivot selection, which production implementations always use.
Step by step
- If the sub-array has zero or one element, it is already sorted. Return.
- Choose the rightmost value as the pivot.
- Scan left to right. Maintain a boundary pointer
i: everything at or left ofiis ≤ pivot. - When the scan pointer
jfinds a value ≤ pivot, advanceiand swapa[i]witha[j]. - After the scan, swap the pivot into position
i + 1. It is now in its final sorted position. - Recurse on the left partition (lo to pivot − 1) and the right partition (pivot + 1 to hi).
Worked example
Sorting [8, 3, 1, 7, 0, 5] with Lomuto partitioning (pivot = last element):
| Partition | Pivot | Result | What happened |
|---|---|---|---|
[8, 3, 1, 7, 0, 5] | 5 | [3, 1, 0, 5, 8, 7] | 3, 1, 0 swap left; 5 lands at index 3 |
[3, 1, 0] | 0 | [0, 1, 3] | 0 stays, swaps to front; lands at index 0 |
[1, 3] | 3 | [1, 3] | 1 stays left; 3 lands at index 2 |
[8, 7] | 7 | [7, 8] | 7 swaps to front; lands at index 4 |
Four partitions, done. Each pivot reached its final position in one pass.
When to use it
| Reach for it when | Avoid it when |
|---|---|
| You need average O(n log n) with low constant factors | Worst-case guarantees matter and you cannot randomise |
| Memory is tight (in-place, O(log n) stack) | Stability is required (use merge sort) |
| Cache performance matters (sequential access pattern) | The input is very small (use insertion sort) |
| You are implementing a hybrid sort (introsort falls back to heapsort if depth exceeds 2 log n) | Values are bounded integers and a linear-time sort like counting sort applies |
The code
Every version below uses Lomuto partition with the last element as pivot, matching the animation above.
def quick_sort(a, lo=0, hi=None):
if hi is None:
hi = len(a) - 1
if lo >= hi:
return a
pivot = a[hi]
i = lo - 1
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]
p = i + 1
quick_sort(a, lo, p - 1)
quick_sort(a, p + 1, hi)
return a
nums = [8, 3, 1, 7, 0, 5]
quick_sort(nums)
print(nums)
Common questions
What is the time complexity of quick sort?
O(n log n) on average: each partition divides the array roughly in half, giving log n levels of recursion with O(n) work per level. The worst case is O(n²), which happens when every pivot lands at the extreme end — for example, an already-sorted array with Lomuto partitioning.
Is quick sort stable?
No. The partition swap can move equal values past each other. If stability matters, use merge sort or a stable variant like three-way partitioning with extra bookkeeping.
Why is quick sort faster than merge sort in practice?
Quick sort sorts in place (O(log n) stack space vs O(n) buffer), so it is more cache-friendly: it reads and writes memory that is already in the CPU cache. Merge sort’s auxiliary buffer causes more cache misses. The constant factors in quick sort’s inner loop are also smaller.
What is the Lomuto partition scheme?
It picks the last element as the pivot and scans left to right with one pointer (j). A second pointer (i) tracks the boundary between values ≤ pivot and values > pivot. When j finds a small value, i advances and the two positions swap. At the end, the pivot swaps into position i+1. It is simpler to implement than Hoare’s scheme but does more swaps on average.
How do you avoid the O(n²) worst case?
Use randomised pivot selection (pick a random element and swap it to the end before partitioning), or median-of-three (take the median of the first, middle and last values). Both make the pathological sorted-input case astronomically unlikely.
Should I use quick sort in real code?
Your language’s built-in sort is almost certainly a hybrid that uses quick sort internally (C’s qsort, Go’s pdqsort, Rust’s slice::sort_unstable). Use the built-in. Implement quick sort yourself only when you need to understand it, or when you need an unstable in-place sort in a constrained environment with no standard library.