# 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)$$?

• This question should have been asked before on this site. How much have you tried searching using the search bar at the top of the page? – John L. Jun 23 '19 at 18:27
• The condition "each appearing $n/k$ times" can be removed. You can consider this as a hint. – John L. Jun 23 '19 at 18:29
• What have you tried? Where are you stuck? Please demonstrate your effort in the question. – John L. Jun 23 '19 at 18:31
• Hint: how many ways are there to arrange n/k copies of k distinct elements? You only need an asymptotic lower bound. – Steven Jun 25 '19 at 14:27
• 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. – John L. Jun 27 '19 at 14:11