TY - JOUR
TI - On sorting networks
DO - https://doi.org/doi:10.7282/t3-ctgk-1j54
AU - Paull, Marvin C.
AU - Levy, Saul
PY - 1972-11
AB - 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.
LA - English
ER -