3
$\begingroup$

In The Art Of Computer Programming, Volume 3, Chapter 5.3.1, Problem 26, Knuth asks one to construct a sorting method that achieves the minimum number of average comparisons for n=7. This means that one needs to find a sorting tree that minimises the total length of all paths from root to every leaf (also known as external path length). A leaf node represents one of the n! permutations of n elements. The average number of comparisons over all possible inputs (all n! permutations) is then simply the external path length divided by n!. The minimal external path length for n=7 is known to be 62416, due to L. Kollar, "Optimal sorting of seven element sets", 1986. Kollar does not seem to construct a sorting tree that achieves this, he only shows that one cannot do better than 62416. Does anyone know whether such a sorting tree has been constructed or is it still an open problem?

Secondary question. How many comparisons does the best known method achieve for n=8? The lower bound for n=8 is 619904, but it is not known if it is obtainable.

$\endgroup$
  • $\begingroup$ IIRC, Knuth lists optimal sorting networks for some $n$. See also here where I dug out the necessary references for $n=5$. $\endgroup$ – Raphael Jun 11 '15 at 8:20
  • $\begingroup$ @Raphael In "Optimal sorting of seven element sets", L. Kollar writes "Knuth (pp. 197 and 630 in TAOCP) gives pls = 62416 for the best known algorithm." However, the author cites the first edition of Volume 3. It may be worth a check. (I don't find this part in the second edition.) $\endgroup$ – hengxin Jun 11 '15 at 9:03
  • $\begingroup$ @hengxin I've seen this reference to the first edition, but can't find it anywhere. Would be great if someone could check. $\endgroup$ – Dmitry Kamenetsky Jun 11 '15 at 10:58
  • $\begingroup$ I'm a bit confused by the question. First you state "the minimal external path length for n=7 is known to be 62416, due to L. Kollar", but then you say that Kollar does not construct a sorting tree that achieves this, only that 62416 is an upper bound. So how do you know that the minimal external path for n=7 is 62416? Is that statement a quotation from some source? If so, what's the source? $\endgroup$ – D.W. Jun 12 '15 at 19:29
  • 1
    $\begingroup$ Thank you, I understand. But again: your post states "The minimal external path length for n=7 is known to be 62416, due to L. Kollar". Where are you getting that from? Is that a quotation from some other source? If so, what is the source for that statement? Or is it a claim/interpretation you are making? If so, what is your justification for it? It seems quite odd, because on the one hand you say "What is the minimal external path length for n=7?" and on the other hand in the same question you state "The minimal external path length for n=7 is 62416". That is confusing. $\endgroup$ – D.W. Jun 13 '15 at 3:57

Your Answer

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

Browse other questions tagged or ask your own question.