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.