Sorting a set of $n$ elements containing only $\log n$ unique elements

Question

We have a set of $n$ elements which contains at most $\log n$ different numbers. I want to sort this set faster than $O(n \log n)$. Is it possible?

I tried using a hash table to find the set of $\log n$ unique elements, then sort them in $O(\log n \log \log n)$, after that creating a new array of $n$ element with this array of $\log n$ elements in $O(n)$, but it is not the right answer since using hash table may fail, and the worst case still needs more than $O(n \log n)$.

Is there any algorithm faster than $O(n \log n)$?

Answer 1

Your solution is almost complete. Try replacing the hash table with a comparable data structure, such as a balanced binary search tree. Since the tree will only contain at most $\log n$ elements, all the operations on the tree will take time $O(\log\log n)$, and the resulting algorithm will take time $O(n\log\log n)$.

Any comparison-based algorithm for your problem takes time $\Omega(n\log\log n)$. To see that, notice that there are roughly $(\log n)^n$ different possible relative orderings for your set (the actual number is a bit smaller, but not by much). Any comparison-based decision tree must therefore have depth $\Omega(\log [(\log n)^n]) = \Omega(n\log\log n)$.

If you allow more general algorithms, then you can improve the complexity to randomized $O(n)$ using a hash table, along the lines that you mentioned. Since you can afford a hash table of size $O(n)$ although the occupancy is only $\log n$, the probability that your algorithm exceeds its expected running time significantly will be very, very small.

It is also possible that under a suitable computation model, you can sort you list in deterministic $O(n)$ time. Some people consider this kind of algorithm cheating, though.

Answer 2

You create a sorted array with the unique values. That array has size O (log n). For every array element of your original element, you use binary search in O (log log n) time to find where it belongs in the small area and add it to a linked list of elements with that value; there may be log n insertions taking (log n)^2 time. You can then create the sorted array in O (n) steps. The biggest factor is n x log log n for the binary search.

Instead of an array with binary search you could use a hash table, which is faster on average but with worse worst case. You can avoid the worst case by using a generous size for the hash table, and handle any collisions immediately in an array. This would often work in O (n) and still have O (n log log n) worst case.