O'Reilly logo

Art of Computer Programming, The: Volume 3: Sorting and Searching by Donald E. Knuth

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 {n1 · 1, . . ., nm · m} if and only if it sorts the single permutation mcm . . . 1c1 . The relation x Image 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required