Sort Colors (Dutch National Flag problem)

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.

 

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?

Algorithm:
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
Three-way partition where 3 pointers are used, 1 for left, 1 for right.
Assume that the array has starting point at lo and ending point at hi.


Reference: This picture is from http://algs4.cs.princeton.edu/23quicksort/

It's based on a single left-to-right  pass through the array that maintains a pointer left such that a[lo...left-1] is less than v, a pointer right such that a[right+1,...hi] is greater than v, and a pointer i such that a[left, i-1] are equal to v,  and a[i...right] are not yet examined.

class Solution {
public:
    void sortColors(int A[], int n) {
        int left = 0, right = n-1, i=left, v = 1;
       
        while(i<=right)  //See above picture, needs to make sure i<=right
        {
            if (A[i]>v)
            {
                swap(A[i],A[right]);
                right--;
            }
            else if (A[i]<v)
            {
                swap(A[i],A[left]);
                i++;
                left++;
            }
            else
               i++;           
        }       
    }
};