# 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.