TADM2E 4.25

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

The array will therefore consist of only very few distinct numbers and all others will be repetitions. An idea to sort such an array is the following

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