Time lower bounds for parallel sorting on a mesh-connected processor array (Q1112618)

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.