Accession Number : AD0735901
Title : A Lower Bound for Sorting Networks that Use the Divide-Sort-Merge Strategy.
Descriptive Note : Technical rept. no. 17,
Corporate Author : STANFORD UNIV CALIF STANFORD ELECTRONICS LABS
Personal Author(s) : Van Voorhis,David C.
Report Date : AUG 1971
Pagination or Media Count : 17
Abstract : Let M sub g (g sup(K+1)) represent the minimum number of comparators required by a network that merges g ordered sets containing g sup K members each. In the paper the author proves that M sub g(g(sup K+1))>or= g(m sub g)(g supK)+ the summation from i=2 to g of ((i-1)g/i). From this relation the author is able to show that an N-sorter which uses the g-way divide-sort-merge strategy recursively must contain about N(log to the base 2 of N) squared comparators. (Author)
Descriptors : (*LOGIC CIRCUITS, MATHEMATICAL ANALYSIS), COMPARATORS, NETWORKS, SET THEORY, THEOREMS, COMPUTER LOGIC
Subject Categories : Computer Systems
Distribution Statement : APPROVED FOR PUBLIC RELEASE