Quick Sort Visualization
Quicksort does its work on the way down: pick a pivot, shove everything smaller to its left and everything larger to its right, and the pivot is permanently placed before you have sorted anything else. It is the fastest general-purpose sort in practice and the easiest to get catastrophically wrong, because a bad pivot choice silently turns n log n into n squared.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
int partition(vector<int>& a, int lo, int hi) {
int pivot = a[hi];
int i = lo - 1;
for (int j = lo; j < hi; j++) {
if (a[j] <= pivot) {
i++;
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);
}
int main() {
vector<int> a = {10, 80, 30, 90, 40, 50, 70};
quickSort(a, 0, (int)a.size() - 1);
for (int x : a) cout << x << ' ';
return 0;
}Lomuto partitioning with the last element as pivot — the simplest correct scheme, and the one whose worst case is easiest to trigger.
How it works, step by step
The pivot ends up in its final position
After one partition call, every element left of index p is <= a[p] and everything right is >= it. That means a[p] is exactly where it belongs in the fully sorted array and is never touched again — which is why the recursive calls exclude it.
i marks the boundary of the small region
During the scan, a[lo..i] holds values <= pivot and a[i+1..j-1] holds values > pivot. i starts at lo - 1 because the small region is initially empty. Every time j finds a small value, i advances and the two are swapped, growing the small region by one.
The final swap seats the pivot
When the loop ends, i + 1 is the first slot of the large region. Swapping it with the pivot at hi drops the pivot exactly between the two regions and pushes a large value into the pivot slot, where it correctly belongs.
Recursion sorts the two sides independently
Nothing ever crosses the pivot again, so the left and right subranges are fully independent problems. Unlike merge sort there is no combine step: when both calls return, the range is sorted.
Balance is everything
If each partition splits roughly in half, the depth is log n and the total is n log n. If it splits into 0 and n-1 — which happens when the pivot is always the smallest or largest element — the depth is n and the total is n squared.
Complexity
Each partition is a linear scan, so the total cost is n times the recursion depth; depth is log n only when pivots land near the median, and picking the last element as pivot makes an already-sorted array hit the quadratic worst case every time.
Common bugs
Sorted input is the worst case, not the best
With a[hi] as the pivot, a sorted array always picks the maximum, producing an empty right side and an n-1 left side. Depth becomes n, the runtime becomes quadratic, and on a large array you get a stack overflow before you get an answer. The fix is median-of-three or a random pivot: swap a random index with hi before partitioning.
Recursing on p instead of p - 1
quickSort(a, lo, p) includes the pivot in the left subproblem. Since the pivot is already final, the range never shrinks when the pivot lands at hi, and you recurse forever on the same bounds. Watching the same lo and hi appear on consecutive stack frames identifies this in seconds.
Using < instead of <= in the partition test
if (a[j] < pivot) sends elements equal to the pivot into the large region. On an array where every value is identical, that puts all n-1 elements on one side and drives the same quadratic blowup — a genuinely common failure, since duplicate-heavy data is everywhere. Either keep <=, or switch to three-way partitioning.
Initialising i to lo instead of lo - 1
The small region starts empty, so the boundary must sit one slot before it. Starting at lo makes the first swap exchange an element with itself in the wrong place and shifts the whole partition by one, so the returned index is wrong and elements end up on the wrong side of the pivot.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
Why is quicksort O(n squared) in the worst case?
Because a pivot that is the smallest or largest element splits the array into one empty side and one side of n-1 elements. The recursion then has depth n instead of log n, and each level still does a linear scan, giving n squared total. With last-element pivots, an already-sorted array triggers this on every single call.
How do I avoid quicksort's worst case?
Choose the pivot so an adversary or a sorted input cannot force it to the extreme. Median-of-three (first, middle, last) fixes sorted and reverse-sorted input cheaply; a randomly chosen pivot makes the quadratic case vanishingly unlikely for any fixed input. Production implementations also track recursion depth and switch to heapsort if it gets too deep.
Is quicksort faster than merge sort?
Usually yes on in-memory arrays, despite the worse asymptotic bound. Quicksort partitions in place with sequential memory access and no allocation, while merge sort copies through an O(n) buffer on every level. Merge sort wins when you need stability, guaranteed bounds, or you are sorting linked lists or data larger than memory.
Is quicksort stable?
No. Partitioning swaps elements across long distances, so two equal values can easily end up in the opposite of their original order. Making it stable requires extra space, at which point merge sort is the better choice.