2
$\begingroup$

In his paper The Bose-Nelson Sorting Problem (1973, Chapter 15 of A Survey of Combinatorial theory on page 163 available on Google books), Knuth says that the optimal bound of 5 comparators for a 4-input sorting network comes from an "elementary information-theoretic argument".

Information theory is not a part of my tool set, yet I have to prove this result.

I have managed to construct a 5-comparator network that solves the problem, and am trying to prove that any 4-comparator network does not work.

I have managed to prove that 3 comparators are needed if we want the top output to be the max of all inputs. In fact, for each input, at least three comparators are needed, but I cannot prove that they are different for each output.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ "In his paper, ..." What paper? Please edit your post to include a reference or link to the paper. $\endgroup$
    – Discrete lizard ♦
    Commented Apr 17, 2018 at 10:30
  • $\begingroup$ I added a reference as well as a link to said paper available online. Sorry, I didn't realize it might interest some people. $\endgroup$
    – John Do
    Commented Apr 19, 2018 at 7:58
  • $\begingroup$ It isn't that I think it is particularly interesting, but more that knowing what paper you are reading could be very helpful to answer your question. $\endgroup$
    – Discrete lizard ♦
    Commented Apr 19, 2018 at 8:55

1 Answer 1

Reset to default
3
$\begingroup$

Suppose that there were a network using only 4 comparators. The correct order of the inputs can be recovered by known the result of all 4 comparisons, since given these results, you can simulate the effect of the network. However, there are only $2^4 = 16$ possible results of the comparisons, whereas there are $4! = 24$ possible orders of inputs.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Why does there have to be more possible results of comparisons than order of inputs possible? I feel like this is the same argument as advanced by Knuth, saying there must be over $log_2(n!)$ comparisons. $\endgroup$
    – John Do
    Commented Apr 17, 2018 at 10:23
  • $\begingroup$ Given the outputs of all comparisons, you should be able to deduce the order of the inputs, since given the outputs, you can sort the inputs. $\endgroup$
    – Yuval Filmus
    Commented Apr 17, 2018 at 10:24
  • $\begingroup$ I get the gist of it, but how does one formalize the fact that a sorting algorithm should be able to 'un-sort' back to the original order? $\endgroup$
    – John Do
    Commented Apr 17, 2018 at 12:00
  • 2
    $\begingroup$ If you run all swaps in reverse, then you are unsorting the sorted version to the original order. $\endgroup$
    – Yuval Filmus
    Commented Apr 17, 2018 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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