Algorithm to sort array into K increasing subsets?

Question

Let's say we got an array of size n with real numbers, and a natural number k. n must be multiple of k. We want to sort the array in a way that, when we divide this array into k subsets of equal size, all numbers of a subset should be less or equal than the numbers of the next right subset. In other words, given 1 <= i <= k, the numbers within subset i must be less or equal than the numbers of subset i + 1. However, the numbers within a subset does not need to be sorted.

For example, if we have k = 4 and the following array of size n = 12:

{10,8,2,12,3,9,4,5,11,1,7,6}

One valid solution could be:

{2,3,1,4,5,6,8,9,7,10,12,11}

As we can see all values of the subset {2,3,1} is less than {4,5,6}, which is less than {8,9,7}, and so on.

The condition here is that the complexity of the algorithm should not be worse than O(n log k). This problem is solved by either a Divide and Conquer approach or Min-heaps.

I tried many strategies, such as using the Quicksort partition algorithm and splitting the problem until reaching to a subproblem of size less than n/k, but at the end the complexity becomes O(n log n).

Any suggestions?

Answer 1

First, consider the case when $k$ is a perfect power of $2$. You find the median of the input array in $O(n)$ time using the Selection algorithm. Now take the median as the pivot to partition the array into two equal halves in $O(n)$ time. For each of the halves, we have the same problem to solve, but now we have $k = k/2$. This goes on for $\log_2 k$ steps, and at each level of the recursion, we do a total of $O(n)$ work. Hence, the total cost is $O(n\log k)$.

Now, when $k$ is not a perfect power of $2$, you must ensure the two halves are balanced as far as possible to get the recursion depth bounded by $O(\log k)$. I believe the rest of the details can be worked out by yourself.