Pairwise sorting network

Visualization of the Pairwise sorting network with 16 inputs
Class	Sorting algorithm
Data structure	Array
Worst-caseperformance	${\displaystyle (\log n)(\log n+1)/2}$ parallel time
Worst-casespace complexity	${\displaystyle n(\log n)(\log n-1)/4+n-1}$ space and sequential time
Optimal	No

Thepairwise sorting network is asorting network discovered and published by Ian Parberry in 1992 inParallel Processing Letters.^[1] The pairwise sorting network has the same size (number of comparators) and depth as theodd–even mergesort network. At the time of publication, the network was one of several known networks with a depth of${\displaystyle O({\log }^{2}n)}$. It requires${\displaystyle n(\log n)(\log n-1)/4+n-1}$ comparators and has depth${\displaystyle (\log n)(\log n+1)/2}$.

The sorting procedure implemented by the network is as follows (guided by thezero-one principle):

1. Sort consecutive pairwise bits of the input (corresponds to the first layer of the diagram)
2. 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)
3. Sort the pairs in nondecreasing order using a specialized network (corresponds to the final layers of the diagram)

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.^[2]

 n ← length of array k ← smallest power of two, k ≥ nfor k/2 ≥ p ≥ 1, pin k/2, k/4, k/8, … 4, 2, 1do(these comparisons can all be done in parallel)for 0 ≤ a < n, ain 0, p*2, p*4, p*6, p*8, p*10, …dofor 0 ≤ b < p, bin 0, 1, 2, … p-3, p-2, p-1do       i ← a + b       j ← a + b + pif j < nthen compare and swap elements i and jend iffor k/2 ≥ q ≥ p*2, qin k/2, k/4, k/8, … p*8, p*4, p*2do(these comparisons can all be done in parallel)for 0 ≤ c < n, cin 0, p*2, p*4, p*6, p*8, p*10, …dofor 0 ≤ d < p, din 0, 1, 2, … p-3, p-2, p-1do         i ← c + d + p         j ← c + d + qif j < nthen compare and swap elements i and jend ifrepeat qrepeat p

• Sorting Networks – Archive of web page by the author.

Thisalgorithms ordata structures-related article is astub. You can help Wikipedia byadding missing information.

• v
• t
• e

• Sorting algorithms
• Algorithms and data structures stubs

• All stub articles