# Sorting a list over rounds of binary comparisons

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?

• 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$. Feb 6, 2022 at 7:43

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.