Journal Article

Parberry’s pairwise sorting network revealed


Batcher’s “merge exchange” sorting network, discussed in a previous pearl (Hinze & Martin, 2016), remains one of the best practical algorithms for oblivious sorting, even almost half a century after its inception. So it is surprising that an algorithm with exactly the same level of performance, devised two decades later by Parberry (1992), has been relatively overlooked. Perhaps a reason for its lack of celebrity is that Parberry’s design is not immediately recognizable, whereas the Batcher method has a familiar ring, as a hardwired implementation of merge sort. Here we hope to rectify this imbalance by unravelling Parberry’s algorithm and uncoupling its close relationship to Batcher’s. Interestingly, Parberry derives his network using the zero-one principle (Knuth, 1998). We abandon this traditional method, in favour of a feature of comparison networks that we consider to be more fundamental: monotonicity. We shall see that this property, used before to demystify Batcher’s merger (Hinze & Martin, 2016), also helps to shed some light on Parberry’s design. To keep the pearl reasonably self-contained we start with a quick recap of the notation and Batcher’s construction.

Attached files


Hinze, Ralf
Martin, Clare

Oxford Brookes departments

Faculty of Technology, Design and Environment\School of Engineering, Computing and Mathematics


Year of publication: 2018
Date of RADAR deposit: 2018-10-05

Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

Related resources

This RADAR resource is the Accepted Manuscript of Parberry’s pairwise sorting network revealed


  • Owner: Joseph Ripp
  • Collection: Outputs
  • Version: 1 (show all)
  • Status: Live
  • Views (since Sept 2022): 119