1
$\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.

$\endgroup$
  • 2
    $\begingroup$ "In his paper, ..." What paper? Please edit your post to include a reference or link to the paper. $\endgroup$ – Discrete lizard Apr 17 '18 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 Apr 19 '18 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 Apr 19 '18 at 8:55
2
$\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.

$\endgroup$
  • $\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 Apr 17 '18 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 Apr 17 '18 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 Apr 17 '18 at 12:00
  • 1
    $\begingroup$ If you run all swaps in reverse, then you are unsorting the sorted version to the original order. $\endgroup$ – Yuval Filmus Apr 17 '18 at 12:02

Your Answer

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

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