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.

  • $\begingroup$ If you have an array of length $n$ with only 0, 1, and 2 in it, how would you sort it by hand? $\endgroup$
    – adrianN
    Dec 23 '16 at 21:43
  • $\begingroup$ @evil, yes, this is the question $\endgroup$
    – 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)$


In O (n log k + k^2) you can trivially create an array with all distinct values in the array, for each k the indices of all array elements equal to k. And then you can create the sorted array in another O (n) operations.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.