Pairwise sorting network

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Pairwise sorting network
Visualization of the Pairwise sorting network with 16 inputs
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.[1] 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[edit]

  1. ^ Parberry, Ian (1992), "The Pairwise Sorting Network", Parallel Processing Letters 2 (2,3): 205–211 

External links[edit]