Sort an array of size n

Question

if an array of size n has only 3 values ​​0, 1 and 2 (repeated any number of times), which is the best way to sort them. the best indicates complexity. consider spatial and temporal complexity as

Answer 1

Count the numbers of each number and after that fill the array with the correct values, this is O(n)

Answer 2

It sounds the same as the problem of the national flag of Dijkstra Holland.

If you need a solution that does not use counting, see http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

Answer 3

Unused C-style solution:

 int count[3] = {0, 0, 0}; for (int i = 0; i < n; ++i) ++count[array[i]]; int pos = 0; for (int c = 0; c < 3; ++c) for (int i = array[c]; i; --i) array[pos++] = c; 

Answer 4

Haskell two-line:

 count xs = Map.toList $ Map.fromListWith (+) [ (x, 1) | x <- xs ] countingSort xs = concatMap ( \(x, n) -> replicate nx) (count xs) > countingSort [2,0,2,1,2,2,1,0,2,1] [0,0,1,1,1,2,2,2,2,2]