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
References
Pairwise sorting network Wikipedia(Text) CC BY-SA