In a single traversal and O(n) time O(1) space


#1
void Solution::sortColors(vector<int> &A) {
int n = A.size();
int high = n-1;
int low = 0, mid = 0;
while(mid<=high){
    switch(A[mid]){
        case 0: swap(A[low], A[mid]);
                low++;mid++;
                break;
        case 1: mid++; break;
        case 2: swap(A[mid], A[high]);
                high--;
                break;
            
    }
}

}