Sorting from independently chosen comparisons

Question

I want to sort a list of n items from pairwise comparisons. Each round, I receive k comparisons, one each from k different "arbiters".

The arbiters cannot coordinate, and must choose their comparisons independently from myself and each other. How should they choose their comparisons so that I can sort the list of items in as few rounds as possible?

A naive solution is that each arbiter independently runs quicksort, sending over the corresponding comparisons they make. Ultimately, I'd just be waiting for one arbiter to finish sorting, so this would take O(n*log(n)) rounds for me to sort the list, and I literally receive no benefit from having k arbiter over just a single arbiter.

Another naive solution is each arbiter independently sends over random comparisons. This would result in a coupon collector problem, and would taken on average O(n^2*log(n)/k) rounds for me to get the right comparisons to sort the list. But unless k is in ω(n), this run-time isn't better than O(n*log(n)).

Is there a better solution? Maybe one that uses O(n*log(n)/k) rounds? (i.e. double the arbiters = half the rounds needed)

To be more concrete about the independence of arbiters: ideally, the arbiters would use symmetric randomized strategies. If that's not possible, though, then I'll allow the arbiters to have a strategy meeting one time only at the start.

Also, arbiters have to send exactly the comparisons they make. E.g. an arbiter cannot just sort the entire list themselves, and then send only the comparisons (arr[i] < arr[i+1]) for i=0 to n-2. They have to send each comparison they make as they make it.

Answer 1

I think I have a solution. It's totally symmetric with no coordination.

Each arbiter runs the following algorithm to choose their comparisons.

First, they consider evenly dividing n into k "sections" (e.g. section 1 is from 1 to n/k, section 2 is from n/k+1 to 2n/k, etc.). Then, they randomly choose one of k sections to focus on. Next, they use quickselect to get all the elements that will end up in their section (which takes O(n) comparisons). Finally, they fully sort their section (which takes O(n*log(n)/k) comparisons). After that, they randomly choose another section and repeat.

To get all k sections sorted, it's a coupon collector problem, and takes k*log(k) tries, which, when distributed over k arbiters, will only take log(k) tries.

So the final number of rounds of this approach will be O(n*log(k) + n*log(n)*log(k)/k) = O(n*log(n)*log(k)/k), which gives you an improvement factor of log(k)/k. This can be upgraded to 1/k if the arbiters are allowed to choose at the start which sections they're in charge of.

Answer 2

This sounds quite a bit like a job for sorting networks (a fixed network of rounds that compare two elements and swap them if out of order).