Pairwise sorting network


The pairwise sorting network is a sorting network discovered and published by Ian Parberry in 1992 in Parallel Processing Letters. The pairwise sorting network has the same size and depth as the odd–even mergesort network. At the time of publication, the network was one of several known networks with a depth of. It requires comparators and has depth.
The sorting procedure implemented by the network is as follows :
  1. Sort consecutive pairwise bits of the input
  2. Sort all pairs into lexicographic order by recursively sorting all odd bits and even bits separately
  3. Sort the pairs in nondecreasing order using a specialized network

Relation to Batcher odd-even mergesort

The pairwise sorting network is very similar to the Batcher odd-even mergesort, but differs in the structure of operations. While Batcher repeatedly divides, sorts and merges increasingly longer subsequences, the pairwise method does all the subdivision first, then does all the merging at the end in the reverse sequence. In certain applications like encoding cardinality constraints, the pairwise sorting network is superior to the Batcher network.

Pseudocode

n ← length of array
k ← smallest power of two, k ≥ n

for k/2 ≥ p ≥ 1, p in k/2, k/4, k/8, … 4, 2, 1 do

'
for 0 ≤ a < n, a in 0, p*2, p*4, p*6, p*8, p*10, … do
for 0 ≤ b < p, b in 0, 1, 2, … p-3, p-2, p-1 do
i ← a + b
j ← a + b + p
if j < n then compare and swap elements i and j end if

for k/2 ≥ q ≥ p*2, q in k/2, k/4, k/8, … p*8, p*4, p*2 do

'
for 0 ≤ c < n, c in 0, p*2, p*4, p*6, p*8, p*10, … do
for 0 ≤ d < p, d in 0, 1, 2, … p-3, p-2, p-1 do
i ← c + d + p
j ← c + d + q
if j < n then compare and swap elements i and j end if

repeat q
repeat p