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.
-
2$\begingroup$ "In his paper, ..." What paper? Please edit your post to include a reference or link to the paper. $\endgroup$Discrete lizard– Discrete lizard ♦2018年04月17日 10:30:15 +00:00Commented 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– John Do2018年04月19日 07:58:12 +00:00Commented 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– Discrete lizard ♦2018年04月19日 08:55:18 +00:00Commented Apr 19, 2018 at 8:55
1 Answer 1
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.
-
$\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– John Do2018年04月17日 10:23:24 +00:00Commented 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– Yuval Filmus2018年04月17日 10:24:42 +00:00Commented 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– John Do2018年04月17日 12:00:38 +00:00Commented 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– Yuval Filmus2018年04月17日 12:02:52 +00:00Commented Apr 17, 2018 at 12:02