Time lower bounds for parallel sorting on a mesh-connected processor array
We prove that \((1+\sqrt{6}/2)n\approx 2.22 n\) is a time lower bound independent of indexing schemes for sorting \(n^ 2\) items on an \(n\times n\) mesh-connected processor array. We distinguish between indexing schemes by showing that there exists an indexing scheme which is provably worse than a snake-like row-major indexing for sorting. We also derive lower bounds for various indexing schemes. All these results are obtained by using the chain argument which we provide in this paper.
scientific article; zbMATH DE number 4078825
scientific article