Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Contact Us
Online Help
Domain Status
Man Pages

Virtual Servers

Topology Map

Server Agreement
Year 2038

USA Flag



Man Pages

Manual Reference Pages  -  ALGORITHM::NETWORKSORT (3)

.ds Aq ’


Algorithm::Networksort - Create Sorting Networks.



  use Algorithm::Networksort qw(:all);

  my $inputs = 4;

  # Generate the sorting network (a list of comparators).
  my @network = nw_comparators($inputs);

  # Print the list, and print the graph of the list.
  print nw_format(\@network), "\n";
  print nw_graph(\@network, $inputs), "\n";


This module will create sorting networks, a sequence of comparisons that do not depend upon the results of prior comparisons.

Since the sequences and their order never change, they can be very useful if deployed in hardware, or if used in software with a compiler that can take advantage of parallelism. Unfortunately a sorting network cannot be used for generic run-time sorting like quicksort, since the arrangement of the comparisons is fixed according to the number of elements to be sorted.

This module’s main purpose is to create compare-and-swap macros (or functions, or templates) that one may insert into source code. It may also be used to create images of the sorting networks in either encapsulated postscript (EPS), scalar vector graphics (SVG), or in ascii art format.


None by default. There is only one available export tag, ’:all’, which exports the functions to create and use sorting networks. The functions are nw_algorithms(), nw_algorithm_name(), nw_comparator(), nw_format(), nw_graph(), nw_color(), nw_group(), and nw_sort().



Return a list algorithm choices. Each one is a valid value for the nw_comparator() algorithm key.


Return the full text name of the algorithm, given its key name.


    @network = nw_comparator($inputs);

    @network1 = nw_comparator($inputs, algorithm => $alg);

    @network2 = nw_comparator($inputs, algorithm => $alg, grouping => $grouptype);

Returns a list of comparators that can sort <B>B>$inputs<B>B> items. The algorithm for generating the list may be chosen, but by default the sorting network is generated by the Bose-Nelson algorithm. The different methods will produce different networks in general, although in some cases the differences will be in the arrangement of the comparators, not in their number.

Regardless of the algorithm you use, you may not get the comparators in the best order possible to prevent stalling in a CPU’s pipeline. So a third option, grouping, is available that arranges the comparators in a slightly different order by calling nw_group() and flattening the array of arrays by taking the comparators in order. See also the documentation for nw_group().

The choices for the <B>groupingB> key are
’none’ Return the sequence as generated by the algorithm with no changes. This will also happen if the <B>groupingB> key isn’t present, or if an incorrect (or misspelled) value for <B>groupingB> is used.
’group’ Use the sequence created by nw_group().
’parallel’ Use the sequence created by nw_group() with the group => ’parallel’ option.
The choices for the <B>algorithmB> key are
’bosenelson’ Use the Bose-Nelson algorithm to generate the network. This is the most commonly implemented algorithm, recursive and simple to code.
’hibbard’ Use Hibbard’s algorithm. This iterative algorithm was developed after the Bose-Nelson algorithm was published, and produces a different network ... for generating the comparisons one by one in the order in which they are needed for sorting, according to his article (see below).
’batcher’ Use Batcher’s Merge Exchange algorithm. Merge Exchange is a real sort, in that in its usual form (for example, as described in Knuth) it can handle a variety of inputs. But while sorting it always generates an identical set of comparison pairs per array size, which lends itself to sorting networks.
’bitonic’ Use Batcher’s bitonic algorithm. A bitonic sequence is a sequence that monotonically increases and then monotonically decreases. The bitonic sort algorithm works by recursively splitting sequences into bitonic sequences using so-called half-cleaners. These bitonic sequences are then merged into a fully sorted sequence. Bitonic sort is a very efficient sort and is especially suited for implementations that can exploit network parallelism.
’bubble’ Use a naive bubble-sort/insertion-sort algorithm. Since this algorithm produces more comparison pairs than the other algorithms, it is only useful for illustrative purposes.
’best’ For some inputs, sorting networks have been discovered that are more efficient than those generated by rote algorithms. When ’best’ is specified one of these are returned instead. The term best does not actually guarantee the best network for all cases. It simply means that at the time of this version of the module, the network returned has the lowest number of comparators for the number of inputs. Considerations of parallelism, or of other networks with an equally low comparator count but with a different arrangement are ignored.

Currently more efficient sorting networks have been discoverd for inputs of nine through sixteen, eighteen, and twenty-two. If you choose ’best’ outside of this range the module will fall back to Batcher’s Merge Exchange algorithm.


    $string = nw_format(\@network, $format1, $format2, \@index_base);

Returns a formatted string that represents the list of comparators. There are two sprintf-style format strings, which lets you separate the comparison and exchange portions if you want. The second format string is optional.

The first format string may also be ignored, in which case the default format will be used: an array of arrays as represented in perl.

The network sorting pairs are zero-based. If you want the pairs written out for some sequence other than 0, 1, 2, ... then you can provide that in an array reference.

<B>Example 0: you want a string in the default format.B>

    print nw_format(\@network);

<B>Example 1: you want the output to look like the default format, but one-based instead of zero-based.B>

    print nw_format(\@network,

<B>Example 2: you want a simple list of SWAP macros.B>

    print nw_format(\@network, "SWAP(%d, %d);\n");

<B>Example 3: as with example 2, but the SWAP values need to be one-based instead of zero-based.B>

    print nw_format(\@network,
                "SWAP(%d, %d);\n",

<B>Example 4: you want a series of comparison and swap statements.B>

    print nw_format(\@network,
                "if (v[%d] < v[%d]) then\n",
                "    exchange(v, %d, %d)\nend if\n");

<B>Example 5: you want the default format to use letters, not numbers.B>

    my @alphabase = (a..z)[0..$inputs];

    my $string = [ .
                "[%s,%s],",      # Note that were using the string flag.

    substr($string, -1, 1) = ];    # Overwrite the trailing comma.
    print $string;


Sets the colors of the svg graph parts (eps support will come later). The parts are named.
inputbegin Opening of input line.
inputline The input line.
inputend Closing of the input line.
compbegin Opening of the comparator.
compline The comparator line.
compend Closing of the comparator line.
foreground Default color for the graph as a whole.
background Color of the background. Currently unimplemented in SVG.
All parts not named are reset to ’undef’, and will be colored with the default ’foreground’ color. The foreground color itself has a default value of ’black’. The one exception is the ’background’ color, which has no default color at all.


Returns a string that graphs out the network’s comparators. The format may be encapsulated postscript (graph=>’eps’), scalar vector graphics (graph=>’svg’), or the default plain text (graph=>’text’ or none). The ’text’ and ’eps’ options produce output that is self-contained. The ’svg’ option produces output between <svg> and </svg> tags, which needs to be combined with XML markup in order to be viewed.

    my $inputs = 4;
    my @network = nw_comparators($inputs);

    print qq(<?xml version="1.0" standalone="no"?>\n),
          qq(<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" ),
          nw_graph(\@network, $inputs, graph => svg);

The ’graph’ option is not the only one available. The graphing can be adjusted to your needs using the following options.

Options for ’svg’ only.
namespace Default value: undef. A tag prefix that allows programs to distinguish between different XML vocabularies that have the same tag. If undefined, no tag prefix is used.
Options for ’svg’ and ’eps’ graphs
hz_margin Default value: 18. The horizontal spacing between the edges of the graphic and the sorting network.
hz_sep Default value: 12. The spacing separating the horizontal lines (the input lines).
indent Default value: 9. The indention between the start of the input lines and the placement of the first comparator. The same value spaces the placement of the final comparator and the end of the input lines.
stroke_width Default value: 2. Width of the lines used to define comparators and input lines. Also represents the radii of the endpoint circles.
title Default value: N = $inputs Sorting Network. Title of the graph. It should be a short one-line description.
vt_margin Default value: 21. The vertical spacing between the edges of the graphic and the sorting network.
vt_sep Default value: 12. The spacing separating the vertical lines (the comparators).
Options for the ’text’ graph
inputbegin Default value: o-. The starting characters for the input line.
inputline Default value: ---. The characters that make up an input line.
inputcompline Default value: -|-. The characters that make up an input line that has a comparator crossing over it.
inputend Default value: -o\n. The characters that make up the end of an input line.
compbegin Default value: -^-. The characters that make up an input line with the starting point of a comparator.
compend Default value: -v-. The characters that make up an input line with the end point of a comparator.
gapbegin Default value: (two spaces). The characters that start the gap between the input lines.
gapcompline Default value: | (space vertical bar space). The characters that make up the gap with a comparator passing through.
gapnone Default value: (three spaces). The characters that make up the space between the input lines.
gapend Default value: \n (two spaces and a newline). The characters that end the gap between the input lines.

This is a function called by nw_graph() and optionally by nw_comparators(). The function takes the comparator list and returns a list of comparator lists, each sub-list representing a group of comparators that can be printed in a single column. There is one option available, ’grouping’, that will produce a grouping that represents parallel operations of comparators.

The chances that you will need to use this function are slim, but the following code snippet may represent an example:

    my $inputs = 8;
    my @network = nw_comparators($inputs, algorithm => batcher);
    my @grouped_network = nw_group(\@network, $inputs, grouping=>parallel);

    print "There are ", scalar @network,
        " comparators in this network, grouped into\n",
        scalar @grouped_network, " parallel operations.\n\n";

    foreach my $group (@grouped_network)
        print nw_format($group), "\n";

    @grouped_network = nw_group(\@network, $inputs);
    print "\nThis will be graphed in ", scalar @grouped_network,
        " columns.\n";

This will produce:

    There are 19 comparators in this network, grouped into 6 parallel operations.


    This will be graphed in 11 columns.


Sort an array using the network. This is meant for testing purposes only - looping around an array of comparators in order to sort an array in an interpreted language is not the most efficient mechanism for using a sorting network.

This function uses the <=> operator for comparisons.

    my @digits = (1, 8, 3, 0, 4, 7, 2, 5, 9, 6);
    my @network = nw_comparators(scalar @digits, algorithm => best);
    nw_sort(\@network, \@digits);
    print join(", ", @digits);


Return statistics on the last nw_sort() call. Currently only swaps, a count of the number of exchanges, is returned.

    my(@d, %nw_stats);
    my @digits = (1, 8, 3, 0, 4, 7, 2, 5, 9, 6);
    my @network_batcher = nw_comparators(scalar @digits,
            algorithm => batcher);
    my @network_bn = nw_comparators(scalar @digits,
            algorithm => bosenelson);

    @d = @digits;
    nw_sort(\@network_batcher, \@d);
    %nw_stats = nw_sort_stats();
    print "The Batcher Merge-Exchange network took ",
        $nw_stats{swaps}, " exchanges to sort the array."

    @d = @digits;
    nw_sort(\@network_bn, \@d);
    %nw_stats = nw_sort_stats();
    print "The Bose-Nelson network took ",
        $nw_stats{swaps}, " exchanges to sort the array."


Doug Hoyte provided the code for the bitonic sort algorithm and the bubble sort, and the idea for what became the nw_sort_stats() function.


    Bose and Nelson’s algorithm.

o Bose and Nelson, A Sorting Problem, Journal of the ACM, Vol. 9, 1962, pp. 282-296.
o Joseph Celko, Bose-Nelson Sort, Doctor Dobb’s Journal, September 1985.
o Frederick Hegeman, Sorting Networks, The C/C++ User’s Journal, February 1993.
o Joe Celko, Joe Celko’s SQL For Smarties (third edition). Implementing Bose-Nelson sorting network in SQL.

This material isn’t in either the second or fourth edition of the book.

o Joe Celko, Joe Celko’s Thinking in Sets: Auxiliary, Temporal, and Virtual Tables in SQL.

The sorting network material removed from the third edition of SQL For Smarties seems to have been moved to this book.

    Hibbard’s algorithm.

o T. N. Hibbard, A Simple Sorting Algorithm, Journal of the ACM Vol. 10, 1963, pp. 142-50.

    Batcher’s Merge Exchange algorithm.

o Code for Kenneth Batcher’s Merge Exchange algorithm was derived from Knuth’s The Art of Computer Programming, Vol. 3, section 5.2.2.

    Batcher’s Bitonic algorithm

o Kenneth Batcher, Sorting Networks and their Applications, Proc. of the AFIPS Spring Joint Computing Conf., Vol. 32, 1968, pp. 307-3114. A PDF of this article may be found at <>.

The paper discusses both the Odd-Even Merge algorithm and the Bitonic algorithm.

o Dr. Hans Werner Lang has written a detailed discussion of the bitonic sort algorithm here: <>
o T. H. Cormen, E. E. Leiserson, R. L. Rivest, Introduction to Algorithms, first edition, McGraw-Hill, 1990, section 28.3.
o T. H. Cormen, E. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd edition, McGraw-Hill, 2001, section 27.3.

    Non-algorithmic discoveries

o Ian Parberry, A computer assisted optimal depth lower bound for sorting networks with nine inputs, <>.
o The Evolving Non-Determinism (END) algorithm has found more efficient sorting networks: <>.
o The 18 and 22 input networks found by Sherenaz Waleed Al-Haj Baddar are described in his paper Finding Better Sorting Networks at <>.

    Algorithm discussion

o Donald E. Knuth, The Art of Computer Programming, Vol. 3: (2nd ed.) Sorting and Searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998.
o Kenneth Batcher’s web site (<>) lists his publications, including his paper listed above.


John M. Gamble may be found at
Search for    or go to Top of page |  Section 3 |  Main Index

perl v5.20.3 ALGORITHM::NETWORKSORT (3) 2012-11-20

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.