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