Space and time complexities of balanced sorting on processor arrays

A processor is balanced in carrying out a computation if its computing time equals its I/O time. When the computation bandwidth of a processor is increased, like when multiple processors are incorporated to form an array, the critical question is to what degree the processor's memory must be enlarged in order to alleviate the I/O bottleneck to keep the computation balanced. In this paper, for the sorting problem, we present two balanced algorithms on linearly connected and mesh-connected processor arrays, respectively, and show that they reach the derived lower bounds of memory sizes. We also verify that the time complexities of the algorithms are optimal under their respective hardware constraints.