Three-way partition
Keep three growing blocks: below the pivot on the left, above it on the right, equal in the middle. One pointer walks the unchecked part and throws each value to the block it belongs in. Also known as the Dutch national flag problem.
2951583574
Split the array into values below 5, equal to 5, and above 5. Press play to start.
1function threeWayPartition(a, pivot) {2 let lo = 0, mid = 0, hi = a.length - 1;3 while (mid <= hi) {4 if (a[mid] < pivot) {5 swap(a, lo, mid); lo++; mid++;6 } else if (pivot < a[mid]) {7 swap(a, mid, hi); hi--;8 } else {9 mid++;10 }11 }12}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n | every input: each value is checked once |
| average | n | any input |
| worst | n | at most one swap per value |
| space | 1 | three indexes, in place |
Where it breaks
- Moving mid after a swap from the right. The value swapped in from hi has not been looked at yet, so mid must stay put. Advance it anyway and an unchecked value can end up in the wrong block.
- Quicksort with many duplicates. A two-way partition puts every copy of the pivot on one side and keeps re-sorting them. Pick All equal: a three-way partition finishes it in one pass, which is why it powers quicksort on duplicate-heavy data.
- Order within a block. Swaps jump values over each other, so equal values do not keep their original order. Use a stable method if that matters.