Nine-input sorting network of optimal depth with minimum number of comparators

Question

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.

• greybeard: 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.

Answer 1

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.
(Bert Dobbelaere provides a list of best known sorting networks up to 64 values that looks up to date as of 2025/02.)

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.)

• greybeard: 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).
• greybeard: In Dobbelaere's list, I found inserting CEs in order of decreasing span saves a "sublayer" here&there: in function generateSVG replace (a[1]-a[0])-(b[1]-b[0]) with (b[1]-b[0])-(a[1]-a[0]) (or just add a - before).

Answer 2

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}

• greybeard: The 10-value networks look identical - in the 9-value networks, only the last two stages (lines, in your representations) are the same.