# Minimal number of comparisons - sorting $6$ elements

I've been thinking about sorting $6$ elements with the minimal possible number of comparisons. I can do it in $10$ comparisons but I've no idea if this is optimal. Or is there a better algorithm ?

Algorithm
1. Sort $a_1, a_2, a_3$ and $a_4, a_5, a_6$.
Number of comparisons: $3+3=6$.
2. Merge two subarrays.
Number of comparisons: $3 + 3 - 2 = 4$.
Total number of comparisons: $6 + 4 = 10$.

• Closely related question. In my answer there, I give a reference to the relevant section in TAoCP. What research have you done? Oct 3, 2015 at 10:48
• How does step 2 take only 4 comparisons? ​ ​
– user12859
Oct 3, 2015 at 12:04
• You are right, I am wrong.... How to fix it ? Oct 3, 2015 at 22:31
• See, for example, Daniel Fischer's answer in Exactly how many comparisons does merge sort make?. Oct 4, 2015 at 7:01
• Ok, I know that I was wrong. I think about fixing my algorithm. Oct 4, 2015 at 8:24

According to A036604, 10 comparisons are indeed optimal. The link probably contains a citation to a paper proving this.

• @user40545 I don't know, but I believe you can verify that yourself. Oct 3, 2015 at 8:21
• Ok, hovewer it is sufficient to analyze decison tree to prove optimality ? ($log(6!)\ge 10$) Oct 3, 2015 at 8:22
• @user40545 You can do this calculation and see for yourself. Try to be more independent. Oct 3, 2015 at 8:24
• I thnik you are right, I am too dependent. Oct 3, 2015 at 8:30

TL-DR; $$10$$

Yes, you need to have possibility to ask up to $$10$$ questions to (comparison) sort an array of $$6$$ elements.

However, it is possible to create an optimal algorithm that will require no more than 10 questions in worst case, but in average only $$9.57777$$ questions (in $$416$$ cases $$10$$ comparisons, in $$304$$ cases only $$9$$).

Here is a decision tree for sorting 6 element arrays [a,b,c,d,e,f]. To make it more compressed. I assumed that already $$a , $$c and $$e has been asked (3 comparisons) and in case of false proper pair has been swapped: As you can see, in addition to these 3 comparisons, we need up to 7 more, but often only 6 that gives us the $$9.57777$$ in average.

• Can you perhaps describe how that algorithm works? It would be great to see some elaboration/justification on the number you are listing.
– D.W.
May 3, 2023 at 20:34
• @D.W. it is based on my own research. Not yet published, but you can ping me on priv: [email protected] for more details. May 5, 2023 at 17:54
• @D.W. I've added example decision tree for you. Cheers! May 5, 2023 at 18:14