# 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?
– Raphael
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.

• thanks, my algorithm is ok ? Oct 3, 2015 at 8:19
• @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