I have an array of the size N with K distinct elements.We don't know what the K is. I would like to sort this array in O(kn). I have found this answer and I would like to understand what does exactly @Aidan Connelly was talking about(I'm unable to comment on this answer) I'm getting the array lets say it's (-50, 234567, -50, 2, 2345670, -50) after sorting it I wanna get (-50, -50, -50, 2, 234567, 2345670) let's say I have the code for quicksort-and I want to get only the unique values. what should I do?go over the array and count for each element how many times it appears?and then make a new array out of it and perform the sort on it?and then make a new array that will contain all the elements?sound like I would be just going over and over the array..it seams to me that it won't be O(kn) anymore. Is there a better way to get only the unique values and count how many times they appear and make a sorted array with all the elements?

***In addition K does not have a fixed upper bound unlike the previous question

  • $\begingroup$ Perhaps someone can explain the answer on chat. $\endgroup$ – Yuval Filmus May 6 '18 at 19:28
  • $\begingroup$ @Yuval Filmus actually there is one big difference between those two,and that is that I don't have any bounds on K $\endgroup$ – Liana78 May 6 '18 at 19:37
  • $\begingroup$ The answers there already explain the running time as a function of $n$ and the number of duplicates ($k$, in your notation), so this is a duplicate -- the answers there answer this question too. $\endgroup$ – D.W. May 6 '18 at 19:57