# Number of comparisons in array where each element appears n/k times [duplicate]

Given an array of $$n$$ elements with $$k$$ distinct elements, each appearing $$n/k$$ times, how can I show that the number of comparisons to the sort the array in the worst case is in $$\Omega(n \log k)$$?

## marked as duplicate by Apass.Jack, David Richerby, Evil, Discrete lizard♦Jun 29 at 19:14

• The condition "each appearing $n/k$ times" can be removed. You can consider this as a hint. – Apass.Jack Jun 23 at 18:29
• Possible duplicate of Sorting when there are only O(log n) many different numbers, where the answer deals with the general situation of $k$ distinct elements. – Apass.Jack Jun 27 at 14:11