254. Sort Zeros, Ones and Twos
You are given n values, each 0, 1 or 2. Print them sorted.
A library sort works. So does counting how many of each and printing them out, which is two passes.
The interesting solution is one pass with three pointers, known as the Dutch national flag partition. Keep a boundary for where the zeros end, a boundary for where the twos begin, and one moving index in between. Everything before the first boundary is 0, everything after the second is 2, and the middle settles into 1s on its own.
That partition is the same operation quicksort performs at every level, which is why it is worth writing once by hand.
Constraints - `1 ≤ n ≤ 200000` - `each a[i] is 0, 1 or 2`
Input
The first line contains an integer n.
The second line contains n values, each 0, 1 or 2.
Output
Print the n values in non-decreasing order, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.