Cheap and Secure Web Hosting Provider : See Now

# [Answers] Sorting array containing elements from $\{1,\ldots,k\}$ in place in $O(n\log k)$

, ,
Problem Detail:

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?

#### Answered By : Yuval Filmus

Here is an idea. Use a variant of quicksort with a twist:

1. Find the median $m$ in-place in time $O(n)$ (this could jumble the array).
2. Partition the array around $m$ using the quicksort partition routine.
3. 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?