I seek to sort a sequence S of n integers with many duplications, such that the number of distinct integers in S is $O(\log n)$. Give an $O(n \log \log n)$ worst-case time algorithm to sort such sequences. I tried quick-sort, Merge-sort, selection-sort but not getting the required running time. So the question is to design a deterministic algorithm for the problem described.
It is from the book Algorithm Design Manual by Steven Skiena (2nd Ed) problem no 4-23, page no- 154 with some modification.