Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
We need an optimal algorithm in pseudo-code for sorting a sequence of $n$ which has only $k$ distinct numbers ($k$ is not known a Priori).
Can we use Counting Sort to solve this problem in $O(n+k)$ time? I don't think so. Though the time complexity of Counting Sort is $O(n+k)$ but $k$ is the largest element in the input but not the number of distinct elements.
Is there any chance that we can get a linear time algorithm to solve this problem?
It is not possible. As if $k = \Theta(n)$, Hence you can not find a linear algorithm. Anyhow, you can find an algorithm in $O(n + k\log(k))$.
Find maximum in $O(n)$. Then create a hash table to find the $k$ distinct values is $O(n)$. Then sort the $k$ values in $O(k\log(k))$. Notice that the space complexity in this algorithm is $O(\text{largest value})$. However, the time complexity would be $O(n + k\log(k))$.
