1
$\begingroup$

My basic setup is very simple: I'm trying to sort N items now, and later on I'll need to incrementally sort more items. The unique part of the problem is that my item comparison is not a computational process; it's a high-latency external task. But I can run several comparisons in parallel. As a result, the duration of the sort is determined fully by the time needed for the comparisons, and the cost is determined by the number of comparisons. Other operations are essentially free.

Now I can optimize either cost or duration. To optimize for cost, I don't use parallel comparisons. I just get the ordinary O(N log N) comparisons, and also O(N log N) duration. Optimizing for duration is only slightly harder: I just compare every element with every other element in parallel. That's trivially O(N*N) cost, O(1) duration.

But I have a constraint in the number of comparisons C I can run in parallel, and it's significantly lower than N*N. It's even significantly lower than N.

This is not a theoretical problem. The practical implementation has humans involved in the comparison operation, which explains the cost and latency.

My current sketch is to create batches of 7 items. Each batch can be sorted in parallel. I can merge-insert them one batch at a time into the master list. When inserting this batch, I compare the middle element of the batch with the middle element of the master list, and depending on the result I then merge one half of the batch with the whole master list and the other half of the batch with only half the master list. The latter task is most expensive, but I use about C=4 comparisons in parallel for this part.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ First thought: Are sorting networks useful here? They explicitly allow for making a fixed number of comparisons in parallel. (Second thought: But maybe they don't make efficient enough use of the information obtained from each comparison.) $\endgroup$
    – j_random_hacker
    May 1, 2020 at 11:21
  • $\begingroup$ @j_random_hacker: Sorting networks implicitly assume that the cost of each comparison is zero - you have the hardware, you might as well use it in every step. $\endgroup$
    – MSalters
    May 1, 2020 at 11:33
  • $\begingroup$ The AKS sorting network uses $O(n\log n)$ comparisons and has depth $O(\log n)$. Perhaps you were thinking of a different sorting network? $\endgroup$
    – Yuval Filmus
    May 1, 2020 at 13:00

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.