A Lower Bound for Sorting Networks that Use the Divide-Sort-Merge Strategy.

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)

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1971
Accession Number
AD0735901

Entities

People

  • David C. Van Voorhis

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Comparators
  • Instrumentation

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Graph Algorithms and Convex Optimization.
  • Mathematics or Statistics