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

Question

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?

• Yuval Filmus: If it's an assignment then perhaps it's best if you solved it on your own. Are other students also getting outside help?
• user40545: 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.
• Yuval Filmus: It's a "project algorithm". Isn't a project a kind of assignment?
• user40545: Ohh, I could also write invent, come up with.... It is only word.

Answer 1

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?

• user40545: 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}$
• Yuval Filmus: Quicksort is often considered in-place despite having the same performance.
• wchargin: @user40545 Wouldn't just indexing into the array require $\mathcal O(\lg n)$ memory?
• Yuval Filmus: @wchargin We are counting machine words rather than bits. Each machine word holds $O(\log n)$ bits.