ABSTRACT
A sorting network is a more realistic, but less general, model of a parallel computer than a PRAM. A sorting network is built by organizing and connecting comparator modules, or comparators for short, to sort a sequence of numbers. Each comparator has two input and two output “wires,” with the wires holding numerical values. One of the output wires always outputs the smallest input value and the other outputs the largest input value, as depicted in Figure 2.1. The objective is to find a sorting network architecture that only depends on the length of the input sequence and that is independent of the values of the sequence. Therefore, the main difference between sorting networks and traditional comparison-based sorting algorithms is that the sequence of comparisons is set in advance, regardless of the outcome of previous comparisons.
