I sketch an impractical, theoretical comparison sort.

  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 minimal 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.

  • 1
    $\begingroup$ 1. Related, but different: you might enjoy reading about Knuth's optimal strategy for solving Mastermind: en.wikipedia.org/wiki/… 2. A possible point of approach towards this problem might be to look at small values of $n$ and exhaustively compute the effectiveness of this strategy and of the optimal strategy. You can probably write a program to do that for you, for very small $n$. $\endgroup$ – D.W. Jul 20 '16 at 20:54
  • $\begingroup$ @D.W. For what it's worth, I did compute it exhaustively up to $n = 12$ and it was optimal (in fact identical to Ford-Johnson's merge-insertion sort). $\endgroup$ – orlp Aug 24 '16 at 1:29
  • $\begingroup$ Cool! That would be a useful thing to mention in the question. $\endgroup$ – D.W. Aug 24 '16 at 2:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.