# Optimal 4-input sorting network

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.

• "In his paper, ..." What paper? Please edit your post to include a reference or link to the paper. – Discrete lizard Apr 17 '18 at 10:30
• I added a reference as well as a link to said paper available online. Sorry, I didn't realize it might interest some people. – John Do Apr 19 '18 at 7:58
• 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. – Discrete lizard Apr 19 '18 at 8:55

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.
• 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. – John Do Apr 17 '18 at 10:23