Pairwise sorting network

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 size (number of comparators) and depth as the odd–even mergesort network. At the time of publication, the network was one of several known networks with a depth of . It requires comparators and has depth .

Pairwise sorting network
Visualization of the Pairwise sorting network with 16 inputs
ClassSorting algorithm
Data structureArray
Worst-case performance parallel time
Worst-case space complexity non-parallel time

The sorting procedure implemented by the network is as follows (guided by the zero-one principle):

  1. Sort consecutive pairwise bits of the input (corresponds to the first layer of the diagram)
  2. Sort all pairs into lexicographic order by recursively sorting all odd bits and even bits separately (corresponds to the next 14 layers of the diagram)
  3. Sort the pairs in nondecreasing order using a specialized network (corresponds to the final layers of the diagram)

Pseudocode

Given the number n of elements to sort, this is one possible non-recursive technique to calculate the index values of the elements to sort:

  # given a positive integer n, being the number of elements to sort
  # note: subscripts are numbered from 0 to (n-1)
  a = 1;
  while (a < n)
    b = a
    c = 0
    while (b < n)
      #### Compare and sort elements with indices (b-a) and (b)  ####
      b = b+1
      c = mod(c+1, a)
      if (c==0), then b = b+a
    end loop (b)
    a = 2*a
  end loop (a)
  
  a = floor(a/4);
  e = 1;
  while (a > 0)
    d = e;
    while (d > 0)
      b = (d+1) * a
      c = 0
      while (b < n)
        #### Compare and sort elements with indices (b-d*a) and (b)  ####
        c = mod (c+1, a)
        b = b+1
        if (c ==0), then b = b+a
      end loop (b)
      d = floor (d/2);
    end loop(d)
    a = floor (a/2);
    e = e*2 + 1;
  end loop(a)

Relation to Batcher odd-even mergesort

The pairwise sorting network is very similar to the Batcher odd-even mergesort, but differs in the structure of operations. While Batcher repeatedly divides, sorts and merges increasingly longer subsequences, the pairwise method does all the subdivision first, then does all the merging at the end in the reverse sequence. In certain applications like encoding cardinality constraints, the pairwise sorting network is superior to the Batcher network.[2]

References
  1. Parberry, Ian (1992), "The Pairwise Sorting Network" (PDF), Parallel Processing Letters, 2 (2, 3): 205–211
  2. http://ianparberry.com/research/sortingnetworks/



This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.