Find an algorithm for sorting integers with time complexity O(n + k*log(k))

Here is a possible solution:

• Using a hash table, count the number of unique values and the number of duplicates of each value. This should have a complexity of O(n).

• Enumerate the hashtable, storing the unique values into a temporary array. Complexity is O(k).

• Sort this array with a standard algorithm such as mergesort: complexity is O(k.log(k)).

• Create the resulting array by replicating the elements of the sorted array of unique values each the number of times stored in the hash table. complexity is O(n) + O(k).

• Combined complexity is O(n + k.log(k)).

For example, if k is a small constant, sorting an array of n values converges toward linear time as n becomes larger and larger.

If during the first phase, where k is computed incrementally, it appears that k is not significantly smaller than n, drop the hash table and just sort the original array with a standard algorithm.