Editing Sorting network (section)

==Introduction==
[[File:Sorting-network-comparator-demonstration.svg|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 {{mvar|x}} and the bottom wire carries {{mvar|y}}, 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.<ref name="clrs">{{Introduction to Algorithms|1}}</ref>{{rp|635}} 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.

[[File:SimpleSortingNetworkFullOperation.svg|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 [[Parallel computing|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.<ref name="clrs"/>{{rp|636–637}}

=== Insertion and Bubble networks ===
We can easily construct a network of any size recursively using the principles of insertion and selection. Assuming we have a sorting network of size ''n'', we can construct a network of size {{nowrap|''n'' + 1}} by "inserting" an additional number into the already sorted subnet (using the principle underlying [[insertion sort]]). We can also accomplish the same thing by first "selecting" the lowest value from the inputs and then sort the remaining values recursively (using the principle underlying [[bubble sort]]).[[File:Recursive-bubble-sorting-network.svg|200px|thumb|A sorting network constructed recursively that first sinks the largest value to the bottom and then sorts the remaining wires. Based on [[bubble sort]]]]
{|
| style="vertical-align: top;" |
| style="vertical-align: top;" |[[File:Recursive-insertion-sorting-network.svg|200px|thumb|A sorting network constructed recursively that first sorts the first n wires, and then inserts the remaining value. Based on [[insertion sort]]]]
|}The structure of these two sorting networks are very similar. A construction of the two different variants, which collapses together comparators that can be performed simultaneously shows that, in fact, they are identical.<ref name="knuth"/> 
{|
|style="vertical-align: top;"| [[File:Six-wire-bubble-sorting-network.svg|200px|thumb|Bubble sorting network]]
|style="vertical-align: top;"| [[File:Six-wire-insertion-sorting-network.svg|200px|thumb|Insertion sorting network]]
|style="vertical-align: top;"| [[File:Six-wire-pyramid-sorting-network.svg|200px|thumb|When allowing for parallel comparators, bubble sort and insertion sort are identical]]
|}

The insertion network (or equivalently, bubble network) has a depth of {{math|2''n'' - 3}},<ref name="knuth"/> where {{math|''n''}} is the number of values. This is better than the {{math|''O''(''n'' log ''n'')}} time needed by [[random-access machine]]s, but it turns out that there are much more efficient sorting networks with a depth of just {{math|''O''(log<sup>2</sup> ''n'')}}, as described [[#Constructing sorting networks|below]].

===Zero-one principle===

While it is easy to prove the validity of some sorting networks (like the insertion/bubble sorter), it is not always so easy. There are {{math|''n''!}} permutations of numbers in an {{mvar|n}}-wire network, and to test all of them would take a significant amount of time, especially when {{mvar|n}} is large.  The number of test cases can be reduced significantly, to {{math|2<sup>''n''</sup>}}, using the so-called zero-one principle.  While still exponential, this is smaller than {{math|''n''!}} for all {{math|''n'' ≥ 4}}, and the difference grows quite quickly with increasing {{mvar|n}}.

The zero-one principle states that, if a sorting network can correctly sort all {{math|2<sup>''n''</sup>}} sequences of zeros and ones, then it is also valid for arbitrary ordered inputs. This not only drastically cuts down on the number of tests needed to ascertain the validity of a network, it is of great use in creating many constructions of sorting networks as well.

The principle can be proven by first observing the following fact about comparators: when a [[monotonic function|monotonically increasing]] function {{mvar|f}} is applied to the inputs, i.e., {{mvar|x}} and {{mvar|y}} are replaced by {{math|''f''(''x'')}} and {{math|''f''(''y'')}}, then the comparator produces {{math|min(''f''(''x''), ''f''(''y'')) {{=}} ''f''(min(''x'', ''y''))}} and {{math|max(''f''(''x''), ''f''(''y'')) {{=}} ''f''(max(''x'', ''y''))}}. By [[Mathematical induction|induction]] on the depth of the network, this result can be extended to a [[Lemma (mathematics)|lemma]] stating that if the network transforms the sequence {{math|''a''<sub>1</sub>, ..., ''a''<sub>''n''</sub>}} into {{math|''b''<sub>1</sub>, ..., ''b''<sub>''n''</sub>}}, it will transform {{math|''f''(''a''<sub>1</sub>), ..., ''f''(''a''<sub>''n''</sub>)}} into {{math|''f''(''b''<sub>1</sub>), ..., ''f''(''b''<sub>''n''</sub>)}}. Suppose that some input {{math|''a''<sub>1</sub>, ..., ''a''<sub>''n''</sub>}} contains two items {{math|''a<sub>i</sub>'' < ''a<sub>j</sub>''}}, and the network incorrectly swaps these in the output. Then it will also incorrectly sort {{math|''f''(''a''<sub>1</sub>), ..., ''f''(''a''<sub>''n''</sub>)}} for the function

:<math>
f(x) = \begin{cases}
        1\ &\mbox{if } x > a_i \\
        0\ &\mbox{otherwise.}
       \end{cases}
</math>

This function is monotonic, so we have the zero-one principle as the [[Contraposition|contrapositive]].<ref name="clrs"/>{{rp|640–641}}