The basic idea is using two pointers: left boundary, right boundary. Then

```
1) put 0 to the left of the left boundary;
2) put 2 to the right of the right boundary.
```

As the following:

```
left boundary| |right boundary
00000 | 1111111 | 22222222
```

**JAVA Code: Time complexity O(n)**

As each element is only checked once, so the time complexity should be O(n).

```
public void sortColors(int[] nums) {
if (nums == null || nums.length == 0) return;
int left = 0, right = nums.length - 1;// Left, right boundary
for (int i = 0; i <= right; i++) {
if (nums[i] == 0 && i != left)// Only swap if i != left
swap(nums, i--, left++);
else if (nums[i] == 2 && i != right)// Only swap if i != right
swap(nums, i--, right--);
}
}
void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
```