The Periodic Balanced Sorting Network

Martin Dowd, Yehoshua Perl, Larry Rudolph, Michael Saks

Research output: Contribution to journalArticlepeer-review

64 Scopus citations

Abstract

A periodic sorting network consists of a sequence of identical blocks. In this paper, the periodic balanced sorting network, which consists of log n blocks, is introduced. Each block, called a balanced merging block, merges elements on the even input lines with those on the odd input lines. The periodic balanced sorting network sorts n items in O1989 time using (n/2)(log n)2 comparators. Although these bounds are comparable to many existing sorting networks, the periodic structure enables a hardware implementation consisting of only one block with the output of the block recycled back as input until the output is sorted. An implementation of our network on the shuffle exchange interconnection model in which the direction of the comparators are all identical and fixed is also presented.

Original languageEnglish (US)
Pages (from-to)738-757
Number of pages20
JournalJournal of the ACM (JACM)
Volume36
Issue number4
DOIs
StatePublished - Jan 10 1989

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'The Periodic Balanced Sorting Network'. Together they form a unique fingerprint.

Cite this