An array $a[1,\ldots,n] \subseteq \{1,\ldots, k\}$ is given, where $k < \sqrt{n}$.Our goal is a project algorithm which sorts it in place and in time $O(n\log k)$.We assume that $k < \sqrt{n}$ - otherwise $O(n\log k) = O(n\log n)$ - then we may use HeapSort.    We may assume that we know $k$.  I try to do it. The only thing that I can do is finding all $k$ distinct elements and bring them on beginning of array in $O(n\log k)$  - I use binary search.    However I have no idea how to solve it. Any ideas?
Sorting array containing elements from $\{1,\ldots,k\}$ in place in $O(n\log k)$
algorithms;sorting;arrays
Here is an idea. Use a variant of quicksort with a twist:Find the median $m$ in-place in time $O(n)$ (this could jumble the array).Partition the array around $m$ using the quicksort partition routine.Divide the array into three parts: smaller than $m$, equal to $m$, and larger than $m$, and recurse on the first and the last.Consider a recursion tree for this algorithm. The tree has depth $\log n$ and $k$ nodes. Imagine compressing the tree by short-circuiting all nodes having only one child. You get a tree with depth $\log k$. Can you justify this short-circuiting and prove a running time of $O(n\log k)$? Or is there a counterexample?