Pairwise sorting network

Pairwise sorting network

300px Visualization of the Pairwise sorting network with 16 inputs
Class	Sorting algorithm
Data structure	Array
Worst case performance	$(\log n)(\log n + 1)/2$ parallel time
Worst case space complexity	$n(\log n)(\log n - 1)/4 + n - 1$ comparators

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 cost (number of comparators) and delay as the odd-even mergesort network. It requires $n(\log n)(\log n - 1)/4 + n - 1$ comparators and has depth $(\log n)(\log n + 1)/2$.

External links

• Sorting Networks – Web page by the author.