Time- and VLSI-optimal Sorting on Meshes with Multiple Broadcasting
D. Bhagavathi, Himabindu Gurla, Stephan Olariu, Jim L. Schwing, W. Shen, Linda F. Wilson, Jinming Zhang · 1993
In this work, we present a time-and VLSI-optimal sorting algorithm for meshes with multiple broadcasting. Specifically, we show that for every choice of a positive integer constant c, m items \left( {n^{\frac{1} {2} + \frac{1} {{2c}}} \leqslant m \leqslant n} \right) stored in the first \left\lceil {\frac{m} {{\sqrt n }}} \right\rceil columns of a mesh with multiple broadcasting of size \sqrt {n} x \sqrt {n} can be sorted in O({\frac{m} {{\sqrt n }}}) time.