4
$\begingroup$

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)

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

2 Answers 2

3
$\begingroup$

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)$.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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