# Sorting an array of length $n$ with $k$ distinct elements

There is an integer array that contain $n$ numbers, in the array there are $k$ distinct elements up to $k = 50$.
Is it possible to sort this array in linear time, by using only comparisons?

I know that comparison sorts cannot perform better than $\mathcal O(n\log n)$, so maybe I have to show a sort function that sort this array in less than $\mathcal O(n\log n)$, and it will be a contradiction.

• If you have an array of length $n$ with only 0, 1, and 2 in it, how would you sort it by hand? – adrianN Dec 23 '16 at 21:43
• @evil, yes, this is the question – Ginger Dec 23 '16 at 21:52

Consider quicksort with $w$ unique values, where the pivot is taken arbitrarily from the list. In the worst case the pivot will be an extrema (either the minimum or maximum of the list), and so the algorithm will recurse for $w-1$ and 1, and a list of 1 unique value is already sorted.
As the time complexity is linear, $O(n)$, for each pass, and the number of passes is in worst case the number of unique values, $O(w)$, then the time complexity is $O(nw)$, which for constant $w=50$, is $O(n)$
So for k with a fixed upper bound, yes, it's easily done in linear time. If k can vary with n, and k is a lot larger than $n^{1/2}$ then you need a slightly more clever algorithm.