Step by step
The example above, written out — the same steps the animation plays.
- 1Start. Quick sort picks a pivot, moves smaller values to its left and larger to its right, then sorts each side the same way.
- 2Pivot 4. Sorting positions 0–6. The last value, 4, is the pivot.
- 3Is 5 < 4?. No — 5 stays on the right side.
- 4Is 3 < 4?. Yes — 3 goes to the left side.
- 5Swap 3 left. 3 swaps with 5 into the "smaller" side.
- 6Is 8 < 4?. No — 8 stays on the right side.
- 7Is 2 < 4?. Yes — 2 goes to the left side.
- 8Swap 2 left. 2 swaps with 5 into the "smaller" side.
- 9Is 9 < 4?. No — 9 stays on the right side.
- 10Is 1 < 4?. Yes — 1 goes to the left side.
- 11Swap 1 left. 1 swaps with 8 into the "smaller" side.
- 12Pivot 4 moves to position 3. Everything left of 4 is smaller; everything right is larger or equal.
- 134 is in its final place. Now sort the left part (0–2) and the right part (4–6) the same way.
- 14Pivot 1. Sorting positions 0–2. The last value, 1, is the pivot.
…and 18 more steps — press Play above to watch them all.
What's happening?
- Take the last value of the range as the pivot.
- Walk through the range: each value smaller than the pivot is swapped into the growing "smaller" side.
- Swap the pivot just after the smaller side — it is now final — and repeat on the left and right parts.
Complexity
- Time
- O(n log n) on average · O(n²) worst case (bad pivots)
- Space
- O(log n) for the recursion
Where you'll meet it
The default in-place sort in many libraries (C's qsort, Java's sort for primitives uses a dual-pivot variant) because it is fast in practice and cache-friendly.
Common mistake
Always taking the last value as pivot on already-sorted data: every split is lopsided and it degrades to O(n²). Real implementations pick random or median-of-three pivots.
FAQ
What is the pivot?
The value the range is split around. After partitioning it sits exactly where it belongs in the sorted list.
Why is the worst case O(n²)?
If the pivot is always the smallest or largest value, each step removes only one value instead of halving the range.
Is quick sort stable?
No — partition swaps can reorder equal values.