Pairwise sorting network

The pairwise sorting network is a <a href="/facts/Sorting_network/ceMfQqSh">sorting network</a> discovered and published by Ian Parberry in 1992 in <a href="/facts/Parallel_Processing_Letters/w0vM8Lyj">Parallel Processing Letters</a>. The pairwise sorting network has the same size (number of comparators) and depth as the <a href="/facts/Batcher_odd%E2%80%93even_mergesort/04xT9Bsk">odd–even mergesort network</a>. At the time of publication, the network was one of several known networks with a depth of 
 
 
 
 O
 (
 
 log
 
 2
 
 
 ⁡
 n
 )
 
 
 {\displaystyle O(\log ^{2}n)}
 
. It requires 
 
 
 
 n
 (
 log
 ⁡
 n
 )
 (
 log
 ⁡
 n
 −
 1
 )
 
 /
 
 4
 +
 n
 −
 1
 
 
 {\displaystyle n(\log n)(\log n-1)/4+n-1}
 
 comparators and has depth 
 
 
 
 (
 log
 ⁡
 n
 )
 (
 log
 ⁡
 n
 +
 1
 )
 
 /
 
 2
 
 
 {\displaystyle (\log n)(\log n+1)/2}
 
.
The sorting procedure implemented by the network is as follows (guided by the <a href="/facts/Sorting_network/ceMfQqSh">zero-one principle</a>):

<ol><li>Sort consecutive pairwise bits of the input (corresponds to the first layer of the diagram)</li>
<li>Sort all pairs into lexicographic order by recursively sorting all odd bits and even bits separately (corresponds to the next three layers of 2+4+8 columns of the diagram)</li>
<li>Sort the pairs in nondecreasing order using a specialized network (corresponds to the final layers of the diagram)</li></ol>

Pairwise sorting network open-in-new

Pairwise sorting network