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

1 Answer 1

Reset to default
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, 2015 at 8:19
  • $\begingroup$ @user40545 I don't know, but I believe you can verify that yourself. $\endgroup$
    – Yuval Filmus
    Oct 3, 2015 at 8:21
  • $\begingroup$ Ok, hovewer it is sufficient to analyze decison tree to prove optimality ? ($log(6!)\ge 10$) $\endgroup$
    – user40545
    Oct 3, 2015 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, 2015 at 8:24
  • $\begingroup$ I thnik you are right, I am too dependent. $\endgroup$
    – user40545
    Oct 3, 2015 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.