Sort Algorithm running in O(n)
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).