The short answer is no, in the worst-case comparison based algorithms, for reasons stated here.
Using a counting technique will at least take $O(n \log n)$ worst case and $O(n \log k)$ if you use a BST. Here I'll give a variant of quick-sort which also achieves $O(n \log k)$ With a slight modification and a more careful analysis of quick-sort. We will change the "pivot" of quick-sort to never put duplicate elements in separate sub-problem. The partition procedure is as follows:
partition(list A of size n):
x = SELECT(A, n/2)
left = list of all elements less than x
right = list of all elements greater than x
center = list of all elements equal to x
return (left, center, right)
Then the overall quick-sort looks like this:
quick-sort(list A of size n):
if all elements in A are the same:
return A
left, center, right = partition(A)
quick-sort(left)
quick-sort(right)
return concat(left, center, right)
The important thing here is the base case, when we only have one unique element in the list, just return the list. This will ensure that we have exactly $k$ leaf nodes in our recursion tree. The recurrence at face-value is:
$$T(n) \leq \max_{i,j} \{T(n - i) + T(n - i - j)\} + O(n)$$
Obviously with some constraints on $i$ and $j$, but that's the idea. Another thing to note is that via SELECT
we ensure that center
contains all the median elements, this would imply that we only recurse on two sub problems of size less than $n/2$, leading us to:
$$T(n) \leq \max_{l,r} \{T(\tfrac{n}{2} - l) + T(\tfrac{n}{2} - r)\} + O(n)$$
Where $l$ would be the overlap of the median on the left side and $r$ would be overlap of median on the right side. Note that $r + l$ is the number of elements equal to the median. With this we see a clear upper bound of $O(n \log n)$. However, when we include the base cases this becomes better. If we assume that each unique element is repeated $c = n/k = n^*/k$ times (distributed evenly) then we can get the recurrence:
$$T(n) \leq \begin{cases}
1 & n \leq n^*/k\\
T(\tfrac{n}{2} - n^*/2k) + T(\tfrac{n}{2} - n^*/2k) + O(n) & \text{otherwise}
\end{cases}$$
If we do recursion tree analysis on this we can see it is $O(n \log k)$.
We could also take advantage of the fact that we do not do $n$ work at each level of recurrence, but rather at level 0 we do $O(n)$, at level 1 we do $O(n - n/k)$, at level 2 we do $O(n - 3n/k)$, at level 3 we do $O(n - 7n/k)$ and so on. Without out our assumption the analysis becomes more tricky, and we would need to do average case analysis. However, I would claim that this assumption is worst case. Intuitively if this assumption did not hold, then we have fewer repetitions for some element $x_i$, but more repetitions for some element $x_j$. Thus, making $x_j$ more likely to be in one of the center
's without going too deep in the recursion tree. This would reduce the amount of work on the remaining subproblem(s)
more by removing more than $n/k$ elements from the list.