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

| cite | improve this question | |
$\endgroup$
  • 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.

| cite | improve this answer | |
$\endgroup$
  • $\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.