5
$\begingroup$

In the research on sorting networks, two parameters are typically of interest: The number of comparators required and the depth required. They have practical implications for throughput and latency. Results in latter category are usually easier to achieve than corresponding results in the former. Already in 1989, Parberry demonstrated that the optimal depth for nine-input and ten-input sorting networks is seven:

Ian Parberry. "A computer assisted optimal depth lower bound for sorting networks with nine inputs." In Proceedings of the 1989 ACM/IEEE Conference on Supercomputing, November 1989, pp.152-161

Not until 2014 was it shown by Codish et. al. that the optimal number of comparators for nine-input sorting networks is 25, while the optimal number of comparators for ten-input sorting networks is 29:

Michael Codish, Luís Cruz-Filipe, Michael Frank, and Peter Schneider-Kamp. "Twenty-five comparators is optimal when sorting nine inputs (and twenty-nine for ten)." In Proceedings 26th IEEE International Conference on Tools with Artificial Intelligence, November 2014, pp. 186-193

In general, sorting networks of optimal depth cannot necessarily be achieved by using the optimal number of comparators. Knuth (TAOCP, Vol. 3, 2nd ed.) states that often "one or two extra comparator modules" are required, and shows (Fig. 51) a ten-input sorting network of optimal depth seven that requires 31 comparators, that is, two more than optimal.

In a multi-hour search of the literature and the internet at large, I have been unable to find a worked-out example of a nine-input sorting network of depth seven, nor have I been able to find information on the minimum number of comparators needed to construct such network. I am currently unable to construct any nine-input sorting networks of optimal depth with my home-grown software.

What nine-input sorting networks of depth seven are known? Following Knuth, they should require no more than 26 or 27 comparators.

$\endgroup$
  • $\begingroup$ (Did you steal a glance at SO?) $\endgroup$ – greybeard Aug 26 '18 at 20:58
  • $\begingroup$ @greybeard I am reasonably active on SO and am not aware of any relevant information there. I would be terribly embarrassed should I have overlooked an answer there and hope that is not the case (in case your question was means as a hint :-). In fact, I asked a different question about nine-input sorting networks there not too long ago, but this one seemed to be a better fit for Computer Science. $\endgroup$ – njuffa Aug 26 '18 at 21:06
  • $\begingroup$ For all I can tell, the nine-input network presented by Ron Zeno does have a depth of seven, and I count 25 modules. I neither tried to form an opinion on whether it sorts nor how it is structurally equivalent to those found in Knuth. $\endgroup$ – greybeard Aug 27 '18 at 21:36
  • $\begingroup$ @greybeard Excellent sleuthing. Please write an answer so I can upvote and accept. The nine-input sorting network by Ron Zeno works. It has 25 comparators, and it has depth seven: SWAP (0, 7); SWAP (1, 6); SWAP (2, 5); SWAP (3, 4); /*1*/ SWAP (0, 3); SWAP (4, 7); SWAP (1, 2); SWAP (6, 8); /*2*/ SWAP (0, 1); SWAP (2, 6); SWAP (3, 4); SWAP (5, 8); /*3*/ SWAP (1, 2); SWAP (3, 5); SWAP (7, 8); SWAP (4, 6); /*4*/ SWAP (1, 3); SWAP (5, 7); SWAP (2, 4); /*5*/ SWAP (0, 1); SWAP (2, 3); SWAP (4, 5); SWAP (6, 7); /*6*/ SWAP (3, 4); SWAP (5, 6); /* depth=7 */ $\endgroup$ – njuffa Aug 27 '18 at 22:24
  • $\begingroup$ While I dither what to present, how to know what I do present, and how to present it, let me plug an article I thought excellent: Daniel Bundala, Michael Codish, Luís Cruz-Filipe, Peter Schneider-Kamp, Jakub Závodný: Optimal-Depth Sorting Networks, JCSS 2017/3, pp.185-204. $\endgroup$ – greybeard Aug 28 '18 at 7:29
3
$\begingroup$

I found a 2002 Reference of the Best-Known Sorting Networks for up to 16 Inputs by Ron Zeno including a diagram of a 9-input network that seems to fit the bill.

His nine-input sorting network of depth seven uses the following arrangement of comparators

{0, 7}, {1, 6}, {2, 5}, {3, 4},
{0, 3}, {1, 2}, {4, 7}, {6, 8},
{0, 1}, {2, 6}, {3, 4}, {5, 8},
{1, 2}, {3, 5}, {4, 6}, {7, 8},
{1, 3}, {2, 4}, {5, 7},
{0, 1}, {2, 3}, {4, 5}, {6, 7},
{3, 4}, {5, 6}


Wolfram demonstrations includes a beta about Sorting Networks, which in due course contains an example of an optimal (module count) nine-input network:

{{1, 2}, {4, 5}, {7, 8}},
{{2, 3}, {5, 6}, {8, 9}},
{{1, 2}, {4, 5}, {7, 8}, {3, 6}},
{{1, 4}, {2, 5}, {6, 9}},
{{4, 7}, {5, 8}, {3, 6}},
{{1, 4}, {2, 5}, {6, 8}, {3, 7}},
{{2, 4}, {5, 7}},
{{3, 5}, {6, 7}},
{{3, 4}}

(That's probably about as close as I will get to providing a visualisation:
looks trivial to plug "the Flensburg" or above 7-level configurations.)

$\endgroup$
  • $\begingroup$ I wasn't able to determine whether the name in one of Hughes 45-comparator networks therein is a typo for Hugues' (Hugues Juillè's). $\endgroup$ – greybeard Aug 31 '18 at 6:02
3
$\begingroup$

In addition to the accepted answer, I found a second example of a nine-input sorting network of optimal depth seven wioth the optimal number of twenty-five comparators on this website. It appears to belong to a German research group and H. W. Lang is listed as the author of the referenced page, which dates to 2014. The arrangement of comparators used is as follows:

{0, 1}, {2, 3}, {4, 5}, {6, 7},
{0, 6}, {1, 7}, {2, 4}, {3, 8},
{0, 2}, {1, 6}, {3, 4}, {5, 8},
{1, 5}, {2, 3}, {4, 6}, {7, 8},
{1, 2}, {3, 4}, {5, 7},
{0, 1}, {2, 3}, {4, 5}, {6, 7},
{3, 4}, {5, 6}

$\endgroup$
  • $\begingroup$ The 10-value networks look identical - in the 9-value networks, only the last two stages (lines, in your representations) are the same. $\endgroup$ – greybeard Sep 7 '18 at 7:10

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.