Sort Algorithm running in O(n) An array A holds n integers, and all integers in A belong to the set {0,1,2}. Describe an O(n) sorting algorithm for putting A in sorted order.
Your algorithm may not make use of auxiliary storage such as arrays or hash tables. More precisely, the only additional space used, beyond the given array is O(1). Give an argument to explain why your algorithm runs in O(n) time.

This is a self-answered question, but other answers are certainly desired.
My answer was the following:

 Algorithm Sort(A, n)
   Input: an array A of n integers, the element of A belong to the set {0,1,2}
   Output: A is sorted
   int zero ← 0, one ← 0
    for i = 0 to n-1
    // we count the number of occurrences of each element in the array
    switch(A[i])
      case 0:
        zero ← zero + 1
      case 1:
        one ← one + 1
    // 2 would be be n - ( zero + one)
    // now we populate the array        
    for i = 0 to n – 1{
      if i &lt; zero then A[i]  = 0
      else if i &lt; zero + 1 then A[i] = 1
      else A[i] = 2


The algorithm traverses the array twice, so its execution time is at least 2n.
I was thinking of a way to get rid of the second for loop, but I doubt it can be avoided, unless the input array is already sorted or it contains element of the same type.
In any case 2n is O(n).