Quicksort
Pick a pivot, move everything smaller to its left, and the pivot lands in its final place. Then do the same to each side. Like sorting a deck by splitting it around one card, over and over.
53819274
Press play or step forward to start.
1function quicksort(a, lo, hi) {2 if (lo >= hi) return;3 const p = partition(a, lo, hi);4 quicksort(a, lo, p - 1);5 quicksort(a, p + 1, hi);6}78function partition(a, lo, hi) {9 const pivot = a[hi];10 let i = lo;11 for (let j = lo; j < hi; j++) {12 if (a[j] < pivot) {13 swap(a, i, j); i++;14 }15 }16 swap(a, i, hi);17 return i;18}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n log n | the pivot splits the range evenly |
| average | n log n | random input |
| worst | n² | sorted input with a last-element pivot |
| space | log n | the recursion stack, on average |
Where it breaks
- Already sorted input. The last element is always the largest, so every split is lopsided. Pick Sorted above and count the compares: 28 for 8 items, the full n(n−1)/2.
- Many duplicates. Equal keys all land on one side. Three-way partitioning fixes it.
- Deep recursion. Recurse into the smaller side first to keep the stack at log n.