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.