4

I sketch an impractical, theoretical comparison sort for sorting array $a$ of size $n$.

  1. Initialize a list of all $n!$ permutations of size $n$.
  2. For each possible pair of indices $i, j$, count how many permutations would get rejected if we were to find out that $a_i < a_j$ or $a_i \nless a_j$ and choose the minimum of these two counts. Finally, choose the pair of indices with the maximal minimum amount of rejections.
  3. For this pair of indices, actually perform the comparison, and remove those permutations from the list that are in conflict with this comparison.
  4. Stop if one permutation remains in the list, otherwise go to 2.

Assuming the input array is selected uniformly from all possible permutations, is this algorithm optimal in comparison count on average?

It's fairly easy to see that the algorithm acquires the most information possible in a single comparison at every comparison. But I have no clue whether this greedy strategy would result in optimal or suboptimal behavior for the entire task.

This question is a cross-post from CS.SE where it hasn't received an answer for 7+ years.

orlp
  • 885
  • 6
  • 13
  • A corollary of Every Poset has a Good Comparison seems to be that each step of your algorithm reduces the number of consistent permutations by at least a constant factor, so that the number of comparisons made by your algorithm in the worst case is $O(n\log n)$, which is optimal up to constant factors even for the average case. – Neal Young Mar 02 '24 at 21:14
  • @NealYoung Right, I am looking for something much stronger however, namely that it is in fact completely optimal. Up until $n = 12$ I have verified that it matches A036604. And not just stronger, also different - the existence of a poset for which this strategy is suboptimal does not automatically mean this strategy is suboptimal for sorting, unless that poset itself can be reached from an initial permutation through this strategy. Weakly solved v.s. strongly solved comes to mind, borrowing from game theory. – orlp Mar 03 '24 at 00:11
  • I guess the worst-case number of comparisons needed (as a function of $n$) is unknown. I'm not sure about the average case, but I would guess it is as well. If so, do you have any ideas for proving optimality without determining the actual number? – Neal Young Mar 03 '24 at 00:53

0 Answers0