Editing Sorting network (section)

===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}}