Large (g,d) Sorting Networks.
Abstract
With only a few exceptions the minimum-comparator N-sorter networks employ the generalized divide-sort-merge strategy. That is, the N inputs are divided among g > or = 2 smaller sorting networks -- of size N1,N2,...,Ng, where N = summation from k = 1 to g of (N sub k) -- that comprise the initial portion of the N-sorter network. The remainder of the N-sorter is a comparator network that merges the outputs of the N1-,N2-,..., and Ng-sorter networks into a single sorted sequence. The most economical merge networks yet designed, known as the (g,d) merge networks, consist of d smaller merge networks -- where d is a common divisor of N1,N2,...Ng -- followed by a special comparator network labeled a (g,d) f-network. The paper describes special constructions for ((2 sup r), (2 sup r)) f-networks. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1971
- Accession Number
- AD0736610
Entities
People
- David C. Van Voorhis
Organizations
- Stanford University