# TADM2E 4.25

From Algorithm Wiki

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

- 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
- 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)) $
- 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