Integer sorting on a mesh-connected array of processors
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.
- Lower bounds for sorting on mesh-connected architectures
- Time lower bounds for parallel sorting on a mesh-connected processor array
- Applications of reconfigurable meshes to constant-time computations
- A mathematical model for mesh's dynamic behavior
- scientific article; zbMATH DE number 3958741 (Why is no real title available?)
- Sorting on a ring of processors
This page was built for publication: Integer sorting on a mesh-connected array of processors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688438)
