thumb|300px|A simple sorting network consisting of four wires and five connectors

In computer science, comparator networks are abstract devices built up of a fixed number of "wires", carrying values, and comparator modules that connect pairs of wires, swapping the values on the wires if they are not in a desired order. Such networks are typically designed to perform sorting on fixed numbers of values, in which case they are called sorting networks.

Sorting networks differ from general comparison sorts in that they are not capable of handling arbitrarily large inputs, and in that their sequence of comparisons is set in advance, regardless of the outcome of previous comparisons. In order to sort a larger number of inputs, new sorting networks must be constructed. This independence of comparison sequences is useful for parallel execution and for implementation in hardware. Despite the simplicity of sorting nets, their theory is surprisingly deep and complex. Sorting networks were first studied circa 1954 by Armstrong, Nelson and O'Connor,

Sorting networks can be implemented either in hardware or in software. Donald Knuth describes how the comparators for binary integers can be implemented as simple, three-state electronic devices. Since the 2000s, sorting nets (especially bitonic mergesort) are used by the GPGPU community for constructing sorting algorithms to run on graphics processing units.

Introduction

thumb|150px|Demonstration of a comparator in a sorting network.

A sorting network consists of two types of items: comparators and wires. The wires are thought of as running from left to right, carrying values (one per wire) that traverse the network all at the same time. Each comparator connects two wires. When a pair of values, traveling through a pair of wires, encounter a comparator, the comparator swaps the values if and only if the top wire's value is greater or equal to the bottom wire's value.

In a formula, if the top wire carries and the bottom wire carries , then after hitting a comparator the wires carry <math>x' = \min(x, y)</math> and <math>y' = \max(x, y)</math>, respectively, so the pair of values is sorted. A network of wires and comparators that will correctly sort all possible inputs into ascending order is called a sorting network or Kruskal hub. By reflecting the network, it is also possible to sort all inputs into descending order.

The full operation of a simple sorting network is shown below. It is evident why this sorting network will correctly sort the inputs; note that the first four comparators will "sink" the largest value to the bottom and "float" the smallest value to the top. The final comparator sorts out the middle two wires.

650px

Depth and efficiency

The efficiency of a sorting network can be measured by its total size, meaning the number of comparators in the network, or by its depth, defined (informally) as the largest number of comparators that any input value can encounter on its way through the network. Noting that sorting networks can perform certain comparisons in parallel (represented in the graphical notation by comparators that lie on the same vertical line), and assuming all comparisons to take unit time, it can be seen that the depth of the network is equal to the number of time steps required to execute it. While an important theoretical discovery, the AKS network has very limited practical application because of the large linear constant hidden by the Big-O notation.

A more recent construction called the zig-zag sorting network of size was discovered by Goodrich in 2014. While its size is much smaller than that of AKS networks, its depth makes it unsuitable for a parallel implementation.

Optimal sorting networks

For small, fixed numbers of inputs , optimal sorting networks can be constructed, with either minimal depth (for maximally parallel execution) or minimal size (number of comparators). These networks can be used to increase the performance of larger sorting networks resulting from the recursive constructions of, e.g., Batcher, by halting the recursion early and inserting optimal nets as base cases. The following table summarizes the optimality results for small networks for which the optimal depth is known:

{| class="wikitable" style="text-align: center;"

|-

! style="text-align: left;" |

| style="width: 20px;" | 1 || style="width: 20px;" | 2 || style="width: 20px;" | 3 || style="width: 20px;" | 4 || style="width: 20px;" | 5 || style="width: 20px;" | 6 || style="width: 20px;" | 7 || style="width: 20px;" | 8 || style="width: 20px;" | 9 || style="width: 20px;" | 10 || style="width: 20px;" | 11 || style="width: 20px;" | 12 || style="width: 20px;" | 13 || style="width: 20px;" | 14 || style="width: 20px;" | 15 || style="width: 20px;" | 16

|17

|-

! style="text-align: left;" | Depth

| 0 || 1 || 3 || 3 || 5 || 5 || 6 || 6 || 7 || 7 || 8 || 8 || 9 || 9 || 9 || 9

|10

|-

! style="text-align: left;" | Size, upper bound

| || || || || || || || || || || || || 43 || 47 || 51 || 55

|60

|}

For larger networks neither the optimal depth nor the optimal size are currently known. The bounds known so far are provided in the table below:

{| class="wikitable" style="text-align: center;"

|-

! style="text-align: left;" |

| style="width: 30px;" | 18 || style="width: 30px;" | 19 || style="width: 30px;" | 20 || style="width: 30px;" | 21 || style="width: 30px;" | 22 || style="width: 30px;" | 23 || style="width: 30px;" | 24 || style="width: 30px;" | 25 || style="width: 30px;" | 26 || style="width: 30px;" | 27 || style="width: 30px;" | 28 || style="width: 30px;" | 29 || style="width: 30px;" | 30 || style="width: 30px;" | 31 || style="width: 30px;" | 32

|-

! style="text-align: left;" | Depth, upper bound

| 11 || 11 || 11 || 12 || 12 || 12 || 12 || 13 || 13 || 13 || 13 || 14 || 14 || 14

|14

|-

! style="text-align: left;" | Depth, lower bound and have been since the 1973 edition; however, while the optimality of the first eight was established by Floyd and Knuth in the 1960s, this property wasn't proven for the final six until 2014 (the cases nine and ten having been decided in 1991

The optimality of the smallest known sorting networks for and was resolved in 2020.

References

  • List of smallest sorting networks for given number of inputs
  • Sorting Networks
  • CHAPTER 28: SORTING NETWORKS
  • Sorting Networks
  • Tool for generating and graphing sorting networks
  • Sorting networks and the END algorithm
  • Sorting Networks validity