BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-71-238
       ENTRY:: November 01, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: A lower bound for sorting networks that use the
               divide-sort-merge strategy
        TYPE:: Technical Report
      AUTHOR:: Van Voorhis, David C.
        DATE:: August 1971
       PAGES:: 15
    ABSTRACT:: Let $M_g (g^{k+1})$ represent the minimum number of
               comparators required by a network that merges g sorted
               multisets containing $g^k$ members each. In this paper we
               prove that $M_g (g^{k+1}) \geq\ g M_g(g^k) + g^{k-1}
               \sum_{\ell =2}^{g} \lfloor (\ell -1)g/\ell\rfloor$. From this
               relation we are able to show that an N-sorter network which
               uses the g-way divide-sort-merge strategy must contain at
               least order $N{(log_2 N)}^2$ comparators.
       NOTES:: [Adminitrivia V1/Prg/19951101]
         END:: STAN//CS-TR-71-238