A Lower Bound for Sorting Networks that Use the Divide-Sort-Merge Strategy.
Technical rept. no. 17,
STANFORD UNIV CALIF STANFORD ELECTRONICS LABS
Pagination or Media Count:
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
- Computer Systems