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

  • 1
    $\begingroup$ 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? $\endgroup$ – John L. Jun 23 '19 at 18:27
  • $\begingroup$ The condition "each appearing $n/k$ times" can be removed. You can consider this as a hint. $\endgroup$ – John L. Jun 23 '19 at 18:29
  • 3
    $\begingroup$ What have you tried? Where are you stuck? Please demonstrate your effort in the question. $\endgroup$ – John L. Jun 23 '19 at 18:31
  • 1
    $\begingroup$ Hint: how many ways are there to arrange n/k copies of k distinct elements? You only need an asymptotic lower bound. $\endgroup$ – Steven Jun 25 '19 at 14:27
  • $\begingroup$ 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. $\endgroup$ – John L. Jun 27 '19 at 14:11