DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
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
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
Distribution Statement:
APPROVED FOR PUBLIC RELEASE