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.
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.
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
