An economical construction for sorting networks
David C. Van Voorhis · 1974
An N-input sorting network, or an N-sorter, is a switching circuit with N outputs that satisfy the following: for any combination of inputs I = {ia, i1, ..., iN-1}, the resulting outputs 0 = {o0, o1, ..., oN-1} are a permutation of I, and o0≤o1≤...;≤oN-1. Batcher shows that a basic 2-sorter, or comparator cell, can be used to construct N-sorters for arbitrary N. For example, the circuit in Figure 1 is a 4-sorter, since comparators A through D move the smallest input to o0 and the largest input to o3, and then comparator E orders the remaining two inputs.