Quick Sort
Quick sort picks one value - the pivot - and splits the array around it: smaller values to the left, bigger to the right. After that split, the pivot is in its final place forever. Then it does the same to both sides. On average it is the fastest comparison sort in practice, because it works in place with tight, cache-friendly loops. Its one weakness: a badly chosen pivot can make it O(n²).
Watch it sort
Press play - or drag the timeline and step through it yourself.18 values. Pick a pivot, put everything smaller on its left, everything bigger on its right, repeat on both sides.
Complexity
The line-up game
A teacher wants to order students by height. She picks one student - the pivot - and says: "Everyone shorter, stand to their left. Everyone taller, to their right." Nobody on the left ever needs to cross to the right again, and the pivot student is now in exactly the right spot. The teacher then plays the same game with the left group and the right group. Each round fixes one student for good and splits the problem in two.
How it works, step by step
Pick a pivot value from the range (the simple version takes the last one).
Walk through the range: every value smaller than the pivot gets swapped into a growing "smaller" zone on the left.
When the walk ends, drop the pivot right after the smaller zone. The pivot is now in its final position - smaller things left, bigger things right.
Now repeat the same steps on the left part and on the right part, separately.
Ranges keep shrinking. A range with one value (or none) is already sorted.
When every range is done, the array is sorted - no merge step needed.
The code, in JavaScript
The clearest version: filter into smaller/bigger, recurse, join. Easy to read - but it copies arrays at every level, so it is for learning, not production.
function quickSort(arr) {
if (arr.length <= 1) return arr;
const [pivot, ...rest] = arr;
const smaller = rest.filter(x => x < pivot);
const bigger = rest.filter(x => x >= pivot);
return [...quickSort(smaller), pivot, ...quickSort(bigger)];
}
quickSort([5, 1, 4, 2]); // → [1, 2, 4, 5]Dry run: sorting [5, 1, 4, 2]
The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.
| Step | Partition | Array | What happened |
|---|---|---|---|
| 1 | 1 | [5, 1, 4, 2] | Partition 1: pivot is 2 (last value of the range). |
| 2 | 1 | [5, 1, 4, 2] | 5 ≥ 2 - belongs on the right side, leave it. |
| 3 | 1 | [5, 1, 4, 2] | 1 < 2 - belongs on the left side. |
| 4 | 1 | [1, 5, 4, 2] | Swap 1 into the left side. |
| 5 | 1 | [1, 5, 4, 2] | 4 ≥ 2 - belongs on the right side, leave it. |
| 6 | 1 | [1, 2, 4, 5] | Move pivot 2 between the sides. |
| 7 | 2 | [1, 2, 4, 5] | Partition 2: pivot is 5 (last value of the range). |
| 8 | 2 | [1, 2, 4, 5] | 4 < 5 - belongs on the left side. |
Good choice when…
- You want the fastest average-case sort for in-memory arrays - tight loops, no extra allocation, very cache-friendly.
- Memory matters: O(log n) stack space versus merge sort's O(n) buffer.
- You only need part of the answer: the same partition idea gives quickselect, which finds the k-th smallest value in O(n) without sorting everything.
Bad choice when…
- You must guarantee a worst case. A hostile or unlucky input makes plain quick sort O(n²); use heap sort or merge sort when the deadline is hard.
- You need stability - partitioning jumps values over each other, so equal items can end up reordered.
- The data is mostly sorted and you use the last element as pivot - that exact combination *is* the worst case.
Common mistakes
- Last-element pivot + already-sorted input = O(n²). Every partition splits into "everything" and "nothing". This is the most common way people hit the worst case in real life - fix it with a random or median-of-three pivot.
- Duplicated values hurt Lomuto: an array of equal items still runs O(n²), because nothing is ever strictly smaller than the pivot. Three-way partitioning (smaller / equal / bigger) fixes it.
- Recursing on both sides can overflow the call stack on huge arrays. Real implementations recurse into the smaller side and loop on the bigger one, capping stack depth at O(log n).
- The pretty `filter`-based version allocates two new arrays per level - O(n log n) extra memory. The speed quick sort is famous for lives only in the in-place version.
Quick Sort vs. its closest relatives
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Quick Sortthis page | O(n log n) | O(n log n) | O(n²) | O(log n) | no |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | yes |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | no |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | no |