*Notes:* If α is a primitive sorting network, so is α^{R} (the comparators in reverse order). For generalizations and another proof of (c), see N. G. de Bruijn, *Discrete Mathematics* **9** (1974), 333–339; *Indagationes Math.* **45** (1983), 125–132. In the latter paper, de Bruijn proved that a primitive network sorts all permutations of the multiset {*n*_{1} · 1, . . ., *n*_{m} · m} if and only if it sorts the single permutation *m*^{cm} . . . 1^{c1} . The relation *x* *y*, defined for permutations *x* and *y* to mean that there exists a standard network α such that *x* = *y*α, is called *Bruhat order*; the analogous relation restricted to primitive α is *weak Bruhat order* (see the answer to ...