9-Input Networks

'floyd09'

A 9-input network of depth 9 discovered by R. W. Floyd. Of interest also because it is using what are essentially three-way comparators split into three sets of two-way comparators.

'senso09'

A 9-input network of depth 8 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

10-Input Networks

'waksman10'

A 10-input network of depth 9 found by A. Waksman.

'senso10'

A 10-input network of depth 8 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

11-Input Networks

'shapirogreen11'

An 11-input network of depth 9 found by G. Shapiro and M. W. Green.

'senso11'

A 11-input network of depth 10 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

12-Input Networks

'shapirogreen12'

A 12-input network of depth 9 found by G. Shapiro and M. W. Green.

'senso12'

A 12-input network of depth 9 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

13-Input Networks

'end13'

A 13-input network of depth 10 generated by the END algorithm, by Hugues Juill�.

'senso13'

A 13-input network of depth 12 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

14-Input Networks

'green14'

A 14-input network of depth 10 created by taking the 16-input network of M. W. Green and removing inputs 15 and 16.

'senso14'

A 14-input network of depth 11 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

15-Input Networks

'green15'

A 15-input network of depth 10 created by taking the 16-input network of M. W. Green and removing the 16th input.

'senso15'

A 15-input network of depth 10 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

16-Input Networks

'green16'

A 16-input network of depth 10 found by M. W. Green.

'senso16'

A 16-input network of depth 10 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

'vanvoorhis16'

From the book Designing Sorting Networks (see "Non-algorithmic discoveries" below).

17-Input Networks

'senso17'

A 17-input network of depth 17 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

'sat17'

17-input network of depth 10 found by M. Codish, L. Cruz-Filipe, T. Ehlers, M. M�ller, P. Schneider-Kamp.

18-Input Networks

'alhajbaddar18'

18-input network of depth 11 found by Sherenaz Waleed Al-Haj Baddar.

'senso18'

A 18-input network of depth 15 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

19-Input Networks

'senso19'

A 19-input network of depth 15 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

20-Input Networks

'sat20'

20-input network of depth 11 found by M. Codish, L. Cruz-Filipe, T. Ehlers, M. M�ller, P. Schneider-Kamp.

'senso20'

A 20-input network of depth 14 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

21-Input Networks

'senso21'

A 21-input network of depth 20 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

22-Input Networks

'alhajbaddar22'

22-input network of depth 12 found by Sherenaz Waleed Al-Haj Baddar.

'senso22'

A 22-input network of depth 15 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

23-Input Networks

'morwenn23'

A 23-input network of depth 18 found by Morwenn, by taking the 24-input network and removing the final input.

'senso23'

A 23-input network of depth 22 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

24-Input Networks

'morwenn24'

A 24-input network of depth 18 found by Morwenn <https://github.com/Morwenn/cpp-sort/wiki/Original-research#sorting-networks-23-and-24>.

Export

Functions

Return the Algorithm::Networksort object, given a key name. Also takes an optional title to override the default.

    $nw = nwsrt_best(name => 'floyd09', title => "Compare depth to Bose-Nelson");

nw_best_names

Return the list of keys for sorting networks of a giving input size.

    @names = nw_best_names(13);

Each name key is a valid option for the name argument of nwsrt_best().

An unlikely example:

    my $inputs = 12;

    for my $name (nwsrt_best_names($inputs))
    {
        my $nw = nwsrt_best(name => $name);
        print $nw->title(), "\n", $nw, "\n";
    }

To get the list of all available names (regardless of input size), simply call the function with no argument:

    my @names = nwsrt_best_names();

nw_best_title

Return a descriptive title for the network, given a name key.

    $title = nw_best_title($key);

These are the titles for the available networks. By themselves, they provide a readable list of choices for an interactive program. They are not to be confused with a sorting network's title, which may be set by the programmer.

Non-algorithmic discoveries

• The networks by Floyd, Green, Shapiro, and Waksman are in Donald E. Knuth's The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.), Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998.
• The Evolving Non-Determinism (END) algorithm by Hugues Juill� has found more efficient sorting networks: <http://www.cs.brandeis.edu/~hugues/sorting_networks.html>.
• The 18 and 22 input networks found by Sherenaz Waleed Al-Haj Baddar are described in her dissertation "Finding Better Sorting Networks" at <http://etd.ohiolink.edu/view.cgi?acc_num=kent1239814529>.
• The 16 input network found by David C. Van Voorhis is described in chapter 5 of Designing Sorting Networks, by Sherenaz W. Al-Haj Baddar and Kenneth E. Batcher.
• The Symmetry and Evolution based Network Sort Optimization (SENSO) found more networks for inputs of 9 through 23.
• Morwenn's 23 and 24-input networks are described at <https://github.com/Morwenn/cpp-sort/wiki/Original-research#sorting-networks-23-and-24>.
• Ian Parberry, "A computer assisted optimal depth lower bound for sorting networks with nine inputs", <http://www.eng.unt.edu/ian/pubs/snverify.pdf>.