visual walkthrough
Sort Colors
Three-way partitioning in one pass; also the core of 3-way quicksort.
The idea
Keep three regions: 0s on the left, 2s on the right, and an unknown middle that `mid` walks through. A 0 is swapped left, a 2 is swapped right, and a 1 is simply passed over.
Every element is placed at most once, so one pass sorts the whole array.
Complexity
| approach | time | space |
|---|---|---|
| Count, then rewrite | O(n) | O(1) |
| Dutch national flag | O(n) | O(1) |