# 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? Commented Dec 23, 2016 at 21:43
• @evil, yes, this is the question Commented Dec 23, 2016 at 21:52

## 3 Answers

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)$

• With a modified balanced search tree, you can achieve $O(n\log k)$.
– user16034
Commented Sep 19, 2023 at 12:53

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.

Create an AVL tree with nodes containing unique integers as keys and their respective counts then simply do inorder traversal

Since there are k distinct integers , the height of tree will grow upto atmost k , evenif k is unknown Each insertion or updation will take logk time , and building this tree will take nlogk Initial insertion is with count 1, if node already exists then simply increment the count of that key Inorder Traversal is O(n) Total time is O(nlogk) You can't do better than O(nlogk) (if k is not known, and without finding k) AVL Sort is best.

If k is known priori or found, then it's O(n) with bucket or count sort. You can determine k in O(n) too