We loop the sequence and maintain that [0, i), [i, j), and [j, k) are 0s, 1s, and 2s sorted in place for [0,k).
An important trick is moving 2 earlier than 1, and 1 earlier than 0.
See the code for details.
public class Solution {
public void sortColors(int[] nums) {
int i = 0;
int j = 0;
for (int k = 0; k < nums.length; ++k) {
int v = nums[k];
nums[k] = 2;
if (v < 2) nums[j++] = 1;
if (v == 0) nums[i++] = 0;
}
}
}