Pairwise sorting network - Alchetron, the free social encyclopedia

Class Sorting algorithm		Data structure Array

Worst-case performance ( log ⁡ n ) ( log ⁡ n + 1 ) / 2 {\displaystyle (\log n)(\log n+1)/2} parallel time Worst-case space complexity n ( log ⁡ n ) ( log ⁡ n − 1 ) / 4 + n − 1 {\displaystyle n(\log n)(\log n-1)/4+n-1} non-parallel time

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 .

References

Pairwise sorting network Wikipedia

(Text) CC BY-SA