Lower bounds for sorting on mesh-connected architectures (Q1091826)

Lower bounds for sorting on mesh-connected arrays of processors are presented. For sorting \(N=n_ 1n_ 2...n_ r\) elements on an \(n_ 1\times n_ 2\times...\times n_ r\) array \(2(n_ 1+...+n_{r-1})+n_ r\) data interchange steps are needed asymptotically. For two dimensions these bounds are asymptotically best possible provided that \(n_ 1\) and \(n_ 2\) are powers of 2. In this case the generalized \(s^ 2\)-way merge sort of Thompson and Kung turns out to be asymptotically optimal. The minimal asymptotic bound of \(2\sqrt{2N}\) interchange steps can be obtained only by sorting algorithms suitable for \(\sqrt{N/2}\times \sqrt{2N}\) meshes. For \(r\geq 3\) dimensions an analysis of aspect-ratios also demonstrates that there exist mesh-connected architectures which are better suited for sorting than simple r-dimensional cubes.