What is a fast algorithm for partitioning an array into $k$ subsets $A_1<\dots<A_n$?

Let $A$ be an array (equipped with a total ordering $\leq$) of size $n = km$ with $k\in \mathbb{N}$, such such that $A,\dots,A[n]$ are all distinct. What is a fast way to find a partition $A_1,\dots,A_k$ of $A$ with $|A_i| = m$ for all $i$, such that $x<y$, if $x\in A_i$ and $y\in A_j$ with $1\leq i<j$?

I have the following rough idea:

1. find the $i\cdot m$-th order statistic for $i = 1,\dots, k$ and put them into an (automatically) ordered list $\operatorname{pvt}$
2. iterate through the elements of $A$ and find for every such element (via binary search) the corresponding interval in $\operatorname{pvt}$ and insert it into the corresponding $A_i$

The first step can be done in $O(nk)$ (finding the $l$-th order statistic can be done in $O(n)$) and the second step in $O(n\log k)$, giving us $O(nk)$ in total.

Is there an obvious faster algorithm? (provided this idea works at all)

• are the numbers in some fixed range ? May 18 '16 at 16:52
• @sasha Well, they don't need to be numbers and there are no further information. May 18 '16 at 16:55

You can do $O(n \log k)$ by finding $mk/2$-order statistic, partitioning the array into two parts of size $mk/2$ and recursing on each side until $k = 1$. You get the recurrence on running time $T(m, k) = 2 T(m,k/2) + \Theta(m k)$ and $T(m, 1) = \Theta(1)$, which solves to $T(m,k) = O(m k \log k) = O(n \log k)$.
• doesn't this only work if $k$ is a power of $2$ or am I missing something? May 18 '16 at 18:02
• It's a standard assumption in divide and conquer. In real code you take $\lfloor k/2 \rfloor$ and $\lceil k/2 \rceil$. This doesn't affect asymptotics because there is always a $k' \ge k$ such that $k' \le 2 k$ and $k'$ is a power of two. Thus, dropping the assumption on $k$ being a power of two only changes the runtime by at most a factor of two, which is swallowed by big-Oh. May 18 '16 at 18:08
• I meant: Can I divide my array into 5 subsets (as opposed to $2,4,8,\dots,$) with this? May 18 '16 at 20:02
• Yes, that's what I meant by my "real code" comment above. In each step you find $\lfloor k/2\rfloor m$ -order statistic, split the array, and recurse. For $k = 5$ you will split the array into $2m$ and $3m$ parts. Then you split the first part into $m$ and $m$, and the second part into $m$ and $2m$. Finally, you split the last part into $m$ and $m$. Done. May 18 '16 at 20:33
What you're describing is similar to the first phase of Samplesort. Counting takes $O(n log k)$, not $O(nk)$. If you want to do the permutation in-place you can look at Cycle Sort; doing it out of place is simpler. Either way that part is $O(n)$.
The number of permutations of a k-way split is ${n!}/{(m!)^k}$, so if we take the log we get $\Omega(n \log k)$ comparisons after a bit of algebra. So there's no faster comparison-based algorithm.