### The periodic balanced sorting networkThe periodic balanced sorting network

Access Restriction
Subscribed

 Author Dowd, Martin ♦ Perl, Yehoshua ♦ Rudolph, Larry ♦ Saks, Michael Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1989 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract A periodic sorting network consists of a sequence of identical blocks. In this paper, the periodic balanced sorting network, which consists of log $\textit{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 $\textit{n}$ items in $\textit{O}([log$ $\textit{n}]2)$ time using $(\textit{n}/2)(log$ $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1989-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 36 Issue Number 4 Page Count 20 Starting Page 738 Ending Page 757

#### Open content in new tab

Source: ACM Digital Library