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?