Report Number: CS-TR-71-238
Institution: Stanford University, Department of Computer Science
Title: A lower bound for sorting networks that use the divide-sort-merge strategy
Author: Van Voorhis, David C.
Date: August 1971
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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/71/238/CS-TR-71-238.pdf