Sorting
Quicksort Visualiser
Partition around a pivot, then sort each side.
Pick a pivot, move everything smaller to its left, then sort each side.
- Comparisons
- 0
- Writes
- 0
- for scale
- n log₂n ≈ 53
A pivot that lands near the middle halves the range, so the partitions stack about log₂n deep. The counter is an exact count for this run; the curve beside it is the shape that count follows as n grows, not a limit on it.
- Being compared
- Being written
- Pivot or smallest so far
- In its final place
- Ruled out
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) { const pivot = a[hi]; let i = lo; for (let j = lo; j < hi; j++) { if (a[j] < pivot) { [a[i], a[j]] = [a[j], a[i]]; i++; } } [a[i], a[hi]] = [a[hi], a[i]]; return i;}The highlighted line is the one that produced the picture on the left.
What Quicksort does
Quicksort picks one value as the pivot and rearranges the range so everything smaller sits to its left and everything else to its right. The pivot is then in its final place, and the two sides can be sorted independently — no merge step is needed, which is why it works in place.
How it works, step by step
- Choose a pivot. This version takes the last value in the range, which is the simplest to follow.
- Walk through the range with a boundary index marking the end of the “smaller than the pivot” region.
- Every value smaller than the pivot is swapped to the boundary, and the boundary moves right.
- Finally swap the pivot to the boundary. It is now in its final position; recurse on the two sides.
What to watch for
- The pivot bar never moves during the scan. Only at the very end does it jump into place, and then it is marked as finished for good.
- A pivot that lands near the middle leaves two balanced halves. A pivot that lands at one end leaves a range only one shorter — that is the O(n²) case.
- Try a sorted array. With the last value as pivot, every partition is maximally unbalanced and the counters explode. Real implementations pick a random or median-of-three pivot precisely to avoid this.
Cost
| Best case | O(n log n) |
|---|---|
| Average | O(n log n) |
| Worst case | O(n²) — a bad pivot every time |
| Extra space | O(log n) for the recursion |
| Stable | No |
When to reach for it
As the default in-memory sort: on typical data it does fewer writes and has better cache behaviour than merge sort, and it needs no second array. Avoid the naive end-of-range pivot in production code, and use merge sort or heap sort when the worst case must be bounded.