Accession Number:

AD0736610

Title:

Large (g,d) Sorting Networks.

Descriptive Note:

Technical rept. no. 18,

Corporate Author:

STANFORD UNIV CALIF STANFORD ELECTRONICS LABS

Personal Author(s):

Report Date:

1971-08-01

Pagination or Media Count:

61.0

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

Subject Categories:

  • Electrical and Electronic Equipment

Distribution Statement:

APPROVED FOR PUBLIC RELEASE