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 parallel time
Worst-case space complexity non-parallel time

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 comparators and has depth .

References[edit]

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

External links[edit]