Just as a reminder as of how slowly the $log(log(n))$ function grows:
 $n$ $log(log(n))$ 10 0.83 100 1.53 1000 1.93 10000 2.22
1. First sweep through the original array and create two auxiliary arrays of numbers $A'=\{ a_1', a_2', a_3', \ldots \}$ (with $\exists~ i,j: a_i=a_j$) and their repetition count $N=\{ n_1, n_2, n_3, \ldots \}$ : this can be done in $O(n)$ time
2. Then sort the two arrays in parallel, comparing keys from $A'$ : this can be done in $O(x\ log(x))$ time with $x=log(log(n))$
3. Finally recreate a sorted version of the original array by taking every number $a_i'$ and repeat it $n_i$ times : this can again be done in $O(n)$ time