The New Class of g-Chain Periodic Sorters

Ronald I. Becker, David Nassimi, Yehoshua Perl

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Aperiodic sorteris a sorting network that is a cascade of a number of identicalblocks, where outputiof each block is inputiof the next block. Previously, Dowd, Perl, Rudolph, and Saks introduced thebalancedmerging network, withN=2kinputs/outputs and logNstages of comparators. Using a very intricate proof, they showed that a cascade of logNsuch blocks constitutes a sorting network. In this paper, we introduce a large class of merging networks with the same periodic property. This class contains 2N/2-1networks, whereN=2kis the number of inputs. The balanced merger is one network in this class. Other networks use fewer comparators. We provide a very simple and elegant correctness proof based on the recursive structure of the networks.

Original languageEnglish (US)
Pages (from-to)206-222
Number of pages17
JournalJournal of Parallel and Distributed Computing
Volume54
Issue number2
DOIs
StatePublished - Nov 1 1998

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Keywords

  • Parallel sorting; merging networks; sorting networks; periodic sorters

Fingerprint Dive into the research topics of 'The New Class of g-Chain Periodic Sorters'. Together they form a unique fingerprint.

Cite this