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