Florian octo Forster's Homepage

Content

• Description
• News
• Download
• See also
• License information

---

Description

libsortnetwork is a C library to work with sorting networks and, more generally, comparator networks. Functions provided by the library include:

• Create well-known constructive networks, for example the Odd-even mergesort network and the Pairwise sorting network.
• Eliminate one or more wires from a network.
• Merge the output from two networks, using the odd-even merge or the bitonic merge networks.
• Normalize a sort networks.
• Write networks to disk and read networks from a file.
• Apply a comparator network to an array of integers.

libsortnetwork is free software and published under the terms of the GNU Lesser General Public License (LGPL), version 2.1.

Also included in the package is a set of command line tools for interactively work with sorting networks. The programs included are:

• sn-apply
  Reads a list of values from STDIN and applies a given comparator network to the list. The resulting list of printed to STDOUT.
• sn-bitonicmerge
  Creates a bitonic merge network with a given number of left and right inputs. The resulting network is printed to STDOUT.
• sn-bitonicsort
  Creates a bitonic mergesort network with a given number of inputs and prints the network to STDOUT.
• sn-check-bf
  Does a brute-force check whether a given comparator network is a sort network. It tries all 2ⁿ 0-1-combinations resulting in exponential running time, so only small networks can be tested within a reasonable time.
• sn-cut
  Remove one or more inputs by assuming positive or negative infinity to be applied to the inputs to remove.
• sn-info
  Display information about a comparator network in human readable form.
• sn-merge
  Combine two sorting networks using the odd-even or bitonic merge network.
• sn-normalize
  Reads a sort network and prints a normalized version to STDOUT. A normalized sort network is a network in which all comparators face the same way.
• sn-oddevenmerge
  Creates an odd-even merge network with a given number of left and right inputs. The resulting network is printed to STDOUT.
• sn-oddevensort
  Creates an odd-even mergesort network with a given number of inputs and prints the network to STDOUT.
• sn-pairwise
  Creates a pairwise sorting network based on the paper by Ian Parberry.
• sn-shmoo
  Prints a so-called “shmoo chart” of a comparator network to STDOUT. The running time of this tool is exponential, roughly O(m · 2ⁿ) where m is the number of stages and n is the number of inputs.
• sn-show
  Prints an ASCII version of a sort network to STDOUT.
• sn-svg
  Prints the Scalable Vector Graphics (SVG) sources of a graphic representation of a comparator network to STDOUT.
• sn-tex
  Prints the TikZ / TeX sources of a graphic representation of a comparator network to STDOUT.
• sn-tex-cut
  Expects a cut-sequence as argument list and reads a network from STDIN. Prints a TikZ / TeX representation of the effect of the cut-sequence on the sorting network to STDOUT.

These utility programs are free software and published under the terms of the GNU General Public License (GPL), version 2.

This library, its tools and the other experimental stuff in the package was developed while and for writing my Diplomarbeit (roughly equivalent to a master's thesis). I don't think I will invest a lot of work in it going forward, but patches, bug reports and questions are welcome anytime, of course.

---

News

• 2011-06-06 Version, 1.1.0, has been released. The tools sn-transpositionsort and sn-tex-cut have been added. Generation of the Pairwise Sorting network for arbitrary n has been fixed.
• 2010-12-21 The initial version, 1.0.0, has been released.

---

Download

• libsortnetwork-1.1.0.tar.bz2 (source tarball)
• libsortnetwork-1.1.0.tar.gz (source tarball)

Development version

The development files are kept in a Git repository. You can “clone” it with the following command. Patches are welcome anytime. :)

A web interface to browse the repository is available, too.

---

See also

• Sorting network page on Wikipedia.

---

License information

libsortnetwork is distributed under the LGPL, version 2.1. Utility programs are distributed under the GPL, version 2. The license can also be found in the COPYING file in the source tarball.