3
$\begingroup$

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

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

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

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.