1
$\begingroup$

You have a list of $n$ items you want to sort over $r$ rounds using binary comparisons. In each round, you specify $k$ binary comparisons to be made in parallel. The objective is to fully sort the list.

For example, if you want to sort in $r\in \Theta(n \log(n))$ rounds, then you only need to make $k=1$ comparison per round (and use any decent algorithm like mergesort). This is the fully sequential case.

If you want to sort in $r=1$ round, you need to make $k\in\Theta(n^2)$ comparisons to successfully sort the list with a probability that doesn't vanish asymptotically (https://cs.stackexchange.com/a/118535/90344). This is the fully parallel case.

Using sorting networks (in particular, the bitonic mergesort network), then one can successfully sort a list in $r\in(\log^2(n))$ rounds with $k=n$ comparisons made per round.

My question is, what is the optimal tradeoff between $r$ and $k$? I.e. if I specify some $r$ (e.g. $r\in\Theta(\sqrt{n})$), then what is the minimum $k$ needed, or vice versa? And what might the accompanying algorithm be?

Lastly, is there aught to be gained by adjusting the number of comparisons made each round? E.g. is it the case that doing more comparisons in earlier rounds (and less in later rounds) will sort the list in fewer overall comparisons/rounds?

$\endgroup$
1
  • $\begingroup$ If you have $n$ comparisons per round, then actually $O(\log n)$ rounds suffice, using the AKS sorting network. This means that you can achieve the optimal $rk = O(n\log n)$ as long as $r\geq C\log n$, for some appropriate constant $C>0$. $\endgroup$ Feb 6, 2022 at 7:43

1 Answer 1

2
$\begingroup$

Your problem is known as sorting in rounds or parallel sorting, first considered by Valiant.

The celebrated AKS sorting network (simplified by Patterson) has depth $\Theta(\log n)$, showing that when $r \geq C\log n$ (for an appropriate constant $C>0$), the optimal number of comparisons per round is $\Theta(n\log n/r)$.

For smaller $r$, the optimum is $\tilde\Theta(n^{1+1/r})$, as shown by Alon and Azar (lower bound) and Bollobás and Thomason (upper bound); the two bounds differ by polylogarithmic factors.

For pointers to the literature, consult Wigderson and Zuckerman, Expanders that beat the eigenvalue bound: explicit constructions and applications.

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