Sorting [log n] different values in linear time

Question

I have an array of n integers that can only assume log n possible values (and any value). For example, in S = [349,12,12,283,349,283,283,12], there are only 3 different numbers (log 8 = 3).

I have to sort this array in less than O(nlogn) time. Which algorithm should I use? Maybe Radix Sort with Counting Sort? What about its analysis?

Answer 1

Since it is a given that there will be only log(n) unique elements, you could get the sorted list in O(n) time using the algorithm below:

1. create a mapping of how many distinct items are there in the list, and keep the count of each (basically a dictionary/hashmap of key, count)
   • This is a single iteration over the input list, so O(n) steps.
2. Sort the above list of tuples of size log(n) based on their key.
   • Say we use merge sort, then the time complexity of merge sort is k*log(k), where k is size of the input.
   • Replacing k with log(n), we get complexity of this step as O(log(n)*log(log(n))).
   • Since in terms of complexity, O(log(n)*log(log(n))) < O(n), so overall complexity till this step is O(n) + O(log(n)*log(log(n))), which is equivalent to O(n) again.
3. Iterate over the sorted keys, and generate the sorted list using a single for loop, wherein each value is repeated by its count. There will be max O(n) iterations here.

So overall, the algorithm above will run in O(n) time.