Sorting array containing elements from $\{1,\ldots,k\}$ in place in $O(n\log k)$
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?