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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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$ – Apass.Jack Jun 23 at 18:27
  • $\begingroup$ The condition "each appearing $n/k$ times" can be removed. You can consider this as a hint. $\endgroup$ – Apass.Jack Jun 23 at 18:29
  • 3
    $\begingroup$ What have you tried? Where are you stuck? Please demonstrate your effort in the question. $\endgroup$ – Apass.Jack Jun 23 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 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$ – Apass.Jack Jun 27 at 14:11