Splitting a group of numbers into $k$ sorted groups

Question

I have this first task:
You have a set of numbers $S =\{ \dots \}$ of length $n$.
And a number $k$.
Both $n$ and $k$ are powers of $2$ and: $1 < k < n$

Your task is to write an algorithm (pseudo-code) that splits $S$ into $k$ sets (which have the same length each): $S_1 , S_2 , \dots, S_k$ such that all the numbers in $S_i$ are smaller than all the numbers in $S_{i+1}$ for all $1 \leq i \leq k-1$ in time complexity of $O(n \cdot k)$ (end of task 1)

The second (another question, but related to the first one) task is the same, but suggesting a faster algorithm - psuedo-code (time complexity -wise)

For example:

For $S = \{11,5,2,7,1,13,15,16 \}$ and $k = 4$ I would return (right to left):
$\{16, 15 \} , \{13, 11 \} , \{5, 7 \} , \{1, 2\}$
notice the order of the numbers inside these sets does not have to be in any particular order.

My go:
What have I not tried.. god:

1. I thought of doing a bucket sort.

2. Maybe choose a random pivot and do a select for each group.

3. Make $k$ empty sets of length $\frac{n}{k}$ each ("in advance") and then choose the $k$-th smaller elements each iteration.

4. make $k$ empty sets of length $\frac{n}{k}$ "in advance" and then putting each number in the first one, and once we come across a bigger number we move the smallest of them to the next set like this for the example above (explicit details below):

This is the algorithm I have so far (number 4):

First we have an empty $k=4$ sets of length $\frac{n}{k} = \frac{8}{4} = 2$ and then comes $11$, then $5$ :
$\{11 , 5 \}, \{ , \}, \{ , \}, \{ , \}$ and then $2$ comes but it's smaller than $5$ or $11$ so $\{11 , 5 \}, \{2 , \}, \{ , \}, \{ , \}$ then comes $7$ and it is larger than $5$ so it replaces it and moves the $5$ to the next set:
$\{11 , 7 \}, \{2 , 5\}, \{ , \}, \{ , \}$ etc...

it should work but I am not sure what is the running complexity. For each set ($k$ times) I have to run $\frac{n}{k}$ iterations (the length of each subset)

Nothing works if I understand it correctly. Nothing here gives me time complexity of $O(n \cdot k)$ ...
I did not even start thinking about the second solution.. because I can't get pass the first one..

I would appreciate your help!

Answer 1

Your second idea seems to be close. Here is the actual algorithm (no random pivot is required):

1. Find the $i{n\over k}$'th order statistic for every $1\le i\le k$. This will take $O(n)$ each time for $k$ values: $O(nk)$.
2. For every such $i$, put all elements with values between the $i{n\over k}$'th and the $(i+1){n\over k}$'th order statistics in the $i$'th bucket. For each $i$ it would cost $O(n)$ and there are $k$ different values for $i$, thus total of $O(nk)$.

Both steps take $O(nk)$ and therefore the entire algorithm runs in $O(nk)$ as required

Hint for the second question: think how you can combine this algorithm with a coarse version of quicksort