Quick sort
mediumAfter one partition the pivot is in its final position forever. Choose 'last element' and feed it a sorted array to watch the O(n²) worst case unfold, then switch to median-of-three and watch it disappear.
O(n log n)Average O(n log n)Worst O(n²)Space O(log n) stackNot stableIn placeSaved in this browser - no sign-up, nothing sent anywhere.
How quick sort works
Pick a pivot and partition: everything smaller ends up left of it, everything larger right, and the pivot itself lands in its final position forever. Then recurse on the two sides. This module uses the Lomuto scheme - the pivot parks at a[hi], an index i tracks the end of the small-values region while j scans, and one last swap drops the pivot at i + 1.
The cost is roughly n comparisons per level times the recursion depth, so everything hinges on the pivot. Balanced splits give log n depth and O(n log n). But feed the default last-element pivot a sorted array and every partition peels off one element: depth n, O(n²), 120 comparisons for 16 values. Switching this visualizer to median-of-three - three extra comparisons per partition - makes that worst case vanish.
Why it is the practical default anyway: it sorts in place with no buffer, and the partition scan walks memory sequentially, so the cache behaviour beats merge sort even though quicksort averages more comparisons. Production versions randomize or median-select pivots and cap recursion depth. It is not stable - partition swaps fling values long distances.
Step by step
- Sort [7, 2, 8, 4, 5] with the last element, 5, as pivot. j scans; i marks the small-values boundary.
- 7 > 5 stays put. 2 <= 5 swaps into the small region: [2, 7, 8, 4, 5].
- 8 > 5 stays. 4 <= 5 swaps with 7: [2, 4, 8, 7, 5]. The scan is done after 4 comparisons.
- The final swap drops the pivot between the regions: [2, 4, 5, 7, 8]. Index 2 is 5's home forever.
- Recurse left on [2, 4]: pivot 4, one comparison, already partitioned. Recurse right on [7, 8]: pivot 8, same story.
- Sorted in 6 comparisons. Run the sorted preset with the last-element pivot and the same code pays the full quadratic price.
Complexity
| Best case time | O(n log n) |
|---|---|
| Average time | O(n log n) |
| Worst case time | O(n²) |
| Space | O(log n) stack |
Balanced partitions give log n depth; a pathological pivot gives n depth.
Reference implementation
Python
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)
quick_sort(a, p + 1, hi)
return a
def partition(a, lo, hi): # Lomuto scheme
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]
return i + 1JavaScript
function quickSort(a, lo = 0, hi = a.length - 1) {
if (lo >= hi) return a;
const p = partition(a, lo, hi);
quickSort(a, lo, p - 1);
quickSort(a, p + 1, hi);
return a;
}
function partition(a, lo, hi) { // Lomuto scheme
const pivot = a[hi];
let i = lo - 1;
for (let j = lo; j < hi; j++) {
if (a[j] <= pivot) { i++; [a[i], a[j]] = [a[j], a[i]]; }
}
[a[i + 1], a[hi]] = [a[hi], a[i + 1]];
return i + 1;
}Java
static void quickSort(int[] a, int lo, int hi) {
if (lo >= hi) return;
int p = partition(a, lo, hi);
quickSort(a, lo, p - 1);
quickSort(a, p + 1, hi);
}
static int partition(int[] a, int lo, int hi) { // Lomuto
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] <= pivot) { i++; swap(a, i, j); }
swap(a, i + 1, hi);
return i + 1;
}C++
int partition(vector<int>& a, int lo, int hi) { // Lomuto
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] <= pivot) swap(a[++i], a[j]);
swap(a[i + 1], a[hi]);
return i + 1;
}
void quickSort(vector<int>& a, int lo, int hi) {
if (lo >= hi) return;
int p = partition(a, lo, hi);
quickSort(a, lo, p - 1);
quickSort(a, p + 1, hi);
}Worth noticing
Partitioning is the entire algorithm
After one partition the pivot is in its final position forever - watch it turn green and never move again. Everything smaller sits left of it, everything larger right. The recursion just repeats that on two smaller problems.
The worst case is a sorted array
Choose 'last element' as the pivot and load the 'sorted' preset. Every partition peels off exactly one element, the recursion depth becomes n, and the comparison count goes quadratic. This is not a theoretical curiosity - it is why naive quicksort implementations get attacked.
Median-of-three fixes the common cases cheaply
Switch the pivot to median-of-three and rerun the sorted array. Three extra comparisons per partition buy back O(n log n) on sorted, reverse-sorted and organ-pipe inputs, which is why real implementations do it.
Fast in practice, despite the worst case
Quicksort does more comparisons than merge sort but no allocation and near-perfect cache locality - it walks memory in straight lines. That constant factor is why it is the default in most standard libraries.
Common pitfalls
- Recursing on ranges that include the pivot - sort(lo, p) instead of sort(lo, p - 1). The pivot is final; re-including it can recurse forever on duplicates.
- Shipping first-or-last pivot selection. Sorted and reversed inputs - common in practice - hit O(n²) and n-deep recursion, and adversaries craft killer inputs deliberately.
- All-equal input with Lomuto: a[j] <= pivot sends every element to one side, so even random data with few unique values goes quadratic. Three-way partitioning - see dutch national flag - is the fix.
- Assuming stability. Partition swaps move values across the whole range, so equal keys reorder - never use plain quicksort for a second-key sort.
- Letting stack depth track the worst case. Real implementations recurse the smaller side and loop the larger, capping the stack at O(log n) even when the splits go bad.
Where it is used
- The engine of unstable library sorts: C's qsort, C++ std::sort via introsort - quicksort until the depth budget runs out, then heap sort - and Rust's sort_unstable via pdqsort.
- Quickselect: the kth smallest element in O(n) average time is one partition, recursing into a single side.
- Duplicate-heavy data via three-way partitioning, the dutch national flag variant.
- The interview centrepiece: partition an array on the whiteboard, then explain the worst case and how to dodge it.
Frequently asked questions
What is the time and space complexity of quicksort?
Best and average case O(n log n) when partitions stay roughly balanced; worst case O(n²) when a pathological pivot - the last element of sorted input, say - peels one element per level. Space is the O(log n) recursion stack on average; the partitioning itself is in place.
Why is quicksort O(n squared) on a sorted array?
With the last element as pivot, everything else is smaller, so the partition splits n elements into n - 1 and 0. The recursion depth becomes n instead of log n, and total comparisons sum to n(n-1)/2. Median-of-three or a random pivot makes balanced splits overwhelmingly likely and restores O(n log n).
Is quicksort stable?
No. Partitioning swaps elements across long distances - watch a small value jump the whole range in one move - so equal keys routinely finish in a different relative order than they started. When stability matters, use merge sort or a library stable sort; stable quicksort variants exist but pay O(n) extra memory.
What is the difference between Lomuto and Hoare partitioning?
Lomuto - used here - parks the pivot at the end, scans once with two indices, and returns the pivot's final position; it is the easiest to prove correct. Hoare runs two pointers inward from both ends, does about three times fewer swaps, but returns a boundary rather than the pivot's final slot, which changes the recursion.