A O( square root N) time sorting algorithm for the mesh connected architecture
Hossam A. ElGindy · 2002
The use of data duplication in systolic architectures to improve the computational time of problems constrained by a large information flow is studied. Its use is demonstrated by presenting an efficient algorithm for sorting N items on a mesh connected computer of N processors. The algorithm has an O(N/sup 1/3/ log N) running time and requires the use of O(N/sup 2/3/) memory locations per processor.>