title: The number of distinct integers in an array is O(log n). How to get an O(n log log n) worst-case time algorithm to sort such sequences?
body: <p>The question is from the The Algorithm Design Manual. I have been working on it but haven't found a method to arrive at the right answer.</p>
  
  <p>Question:
  We 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.</p>
  
  <p>I think maybe can first pick all these distinct elements and form an array of logn length and then record the frequency and sort it. However the my first step seems to blow up running time too much...Is any superior selection method or is my method totally wrong? Thanks</p>