Integer sorting on a mesh-connected array of processors (Q688438)

The problem of sorting is of fundamental importance in computing. In sequential models of computation the difference between sorting general inputs and sorting integers in a fixed range has been well established. In a model where only comparisons between inputs are allowed a lower bound of \(\Omega(N\log N)\) for sorting \(N\) inputs is well known. However if we know the inputs fall in a polynomial-size range, an algorithm with complexity \(O(N)\) is possible. In this paper we study the effect of limiting the inputs to be integers in the range \([1\ldots N]\) in the case of sorting \(N=n^ 2\) inputs on an \(n\times n\) mesh-connected array of processors.