On sorting networks
Marvin C. Paull, Saul Y. Levy · Rutgers University Community Repository (Rutgers University) · 1972
Comparator networks can model many algorithms for internal computer sorting. A comparator network is a (non feedback) switching network built of two-input by the two-output gates whose inputs are drawn from some completely ordered set (for convenience and with no loss of generality in our discussion we take that set to be the non-negative integers), and whose outputs correspond to the maximum of the two inputs on one lead and the minimum on the other. A network consisting exclusively of this type of element can, of course, represent only a subset of the comparator algorithms which could be carried out by a general purpose computer. It cannot, for example, describe algorithms where the comparison tree is altered and pruned as more information becomes available about the ordering of the inputs.