# 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 '15 at 10:48
• How does step 2 take only 4 comparisons? ​ ​ – user12859 Oct 3 '15 at 12:04
• You are right, I am wrong.... How to fix it ? – user40545 Oct 3 '15 at 22:31
• See, for example, Daniel Fischer's answer in Exactly how many comparisons does merge sort make?. – greybeard Oct 4 '15 at 7:01
• Ok, I know that I was wrong. I think about fixing my algorithm. – user40545 Oct 4 '15 at 8:24

• Ok, hovewer it is sufficient to analyze decison tree to prove optimality ? ($log(6!)\ge 10$) – user40545 Oct 3 '15 at 8:22