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:

1971-08-01

Pagination or Media Count:

17.0

Abstract:

Let M sub g g supK1 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 ggsup K1or gm sub gg supK the summation from i2 to g of i-1gi. 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 Nlog 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