Sorting a list over rounds of binary comparisons

Question

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?

Answer 1

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.