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

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?

• If it's an assignment then perhaps it's best if you solved it on your own. Are other students also getting outside help? Nov 13, 2015 at 13:14
• No it isn't assigment. I tried to solve it but I got stuck. I said what I managed to come up with. Clue will be sufficient. Nov 13, 2015 at 13:17
• It's a "project algorithm". Isn't a project a kind of assignment? Nov 13, 2015 at 13:19
• Ohh, I could also write invent, come up with.... It is only word. Nov 13, 2015 at 13:20

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?
• It's ok, but you use additional space $O(\log k)$ (recursion). Algorithm have should worked in place (constant memory). Let's note that you didn't use fact that $k < \sqrt{n}$ Nov 13, 2015 at 17:00
• @user40545 Wouldn't just indexing into the array require $\mathcal O(\lg n)$ memory? Oct 29, 2016 at 22:44
• @wchargin We are counting machine words rather than bits. Each machine word holds $O(\log n)$ bits. Oct 30, 2016 at 0:05