Algorithm to sort n size input with k distinct elements
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))$.