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)

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

2 Answers 2

Reset to default
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)$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ doesn't this only work if $k$ is a power of $2$ or am I missing something? $\endgroup$
    – Stefan Perko
    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$
    – Denis Pankratov
    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$
    – Stefan Perko
    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$
    – Denis Pankratov
    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.

Improve this answer
$\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.