AbstractComparator 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.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).