<p>I sketch an impractical, theoretical comparison sort for sorting array <span class="math-container">$a$</span> of size <span class="math-container">$n$</span>.</p>
<ol>
<li>Initialize a list of all <span class="math-container">$n!$</span> permutations of size <span class="math-container">$n$</span>.</li>
<li>For each possible pair of indices <span class="math-container">$i, j$</span>, count how many permutations would get rejected if we were to find out that <span class="math-container">$a_i &lt; a_j$</span> or <span class="math-container">$a_i \nless a_j$</span> and choose the minimum of these two counts. Finally, choose the pair of indices with the maximal minimum amount of rejections.</li>
<li>For this pair of indices, actually perform the comparison, and remove those permutations from the list that are in conflict with this comparison.</li>
<li>Stop if one permutation remains in the list, otherwise go to 2.</li>
</ol>
<p>Assuming the input array is selected uniformly from all possible permutations, is this algorithm optimal in comparison count on average?</p>
<p>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.</p>
<hr />
<p>This question is a cross-post from <a href="https://cs.stackexchange.com/questions/60807/is-greedy-minimax-permutation-rejecting-sorting-optimal">CS.SE</a> where it hasn't received an answer for 7+ years.</p>

CC BY-SA 4.0
2024-03-02T21:14:43.123Z
A corollary of [Every Poset has a Good Comparison](https://doi.org/10.1145/800057.808694) 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
CC BY-SA 4.0
2024-03-03T00:11:26.497Z
@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](https://oeis.org/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
CC BY-SA 4.0
2024-03-03T00:53:37.583Z
I guess the *worst-case* number of comparisons needed (as a function of $n$) is [unknown](https://cstheory.stackexchange.com/questions/41493/sorting-with-an-average-of-mathrmlgnon-comparisons).  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
<ds.algorithms><sorting><greedy-algorithms>
Is greedy minimax permutation rejecting sorting optimal?
orlp
# Is greedy minimax permutation rejecting sorting optimal?

(Asked by: username_0 on 2024-02-29)

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](https://cs.stackexchange.com/questions/60807/is-greedy-minimax-permutation-rejecting-sorting-optimal) where it hasn't received an answer for 7+ years.

**Tags:** ds.algorithms, sorting, greedy-algorithms

> **Comments:**
> **username_1**: A corollary of [Every Poset has a Good Comparison](https://doi.org/10.1145/800057.808694) 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.  
> **username_0**: @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](https://oeis.org/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.  
> **username_1**: I guess the *worst-case* number of comparisons needed (as a function of $n$) is [unknown](https://cstheory.stackexchange.com/questions/41493/sorting-with-an-average-of-mathrmlgnon-comparisons).  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?  

---

## 0 answers

