Ian Parberry, "The Pairwise Sorting Network". Parallel Processing Letters, Vol. 2, No. 2,3, pp. 205-211, 1992. [pdf]
A new sorting network with exactly the same size and depth as the odd-even sorting network is presented. This sorting network is designed using the zero-one principle, and proceeds by first sorting pairs of bits and sorting the pairs into lexicographic order.
A 2010 paper by Michael Codish and Moshe Zazon-Ivry quotes my paper as saying: "It is the first sorting network to be competitive with the odd-even sort for all values of n. The value of the pairwise sorting network is not that it is superior to the odd-even sorting network in any sense, but that it is the first serious rival to appear in over 20 years", and they go on to say: "In this paper, almost 20 years after the introduction of pairwise sorting networks, we are in the position to state that pairwise sorting networks are significantly superior to odd-even sorting networks, at least for encoding cardinality constraints."
The following supplementary images have the channels drawn horizontally and comparators drawn vertically. The comparators route the smaller of the values on its channels to the upper of the two channels that it is connected to, and the larger of the two values to the lower channel. When the inputs are placed on the channels at thr left of each diagram, the outputs appear in non-decreasing order from top to bottom at the right. These images were produced with the open-source sorting network viewer.
Created November 9, 2022. Last updated November 9, 2022.