Let $A$ be an array (equipped with a total ordering $\leq$) of size $n = km$ with $k\in \mathbb{N}$, such such that $A[1],\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)

  • $\begingroup$ are the numbers in some fixed range ? $\endgroup$ – sashas May 18 '16 at 16:52
  • $\begingroup$ @sasha Well, they don't need to be numbers and there are no further information. $\endgroup$ – Stefan Perko 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)$.

| cite | improve this answer | |
  • $\begingroup$ doesn't this only work if $k$ is a power of $2$ or am I missing something? $\endgroup$ – Stefan Perko May 18 '16 at 18:02
  • $\begingroup$ 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. $\endgroup$ – Denis Pankratov May 18 '16 at 18:08
  • $\begingroup$ I meant: Can I divide my array into 5 subsets (as opposed to $2,4,8,\dots,$) with this? $\endgroup$ – Stefan Perko May 18 '16 at 20:02
  • $\begingroup$ 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. $\endgroup$ – Denis Pankratov 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.