Efficient scalable mesh algorithms for merging, sorting and selection
Sarnath Ramnath · 2002
Efficient scalable algorithms are developed for a mesh with fixed buses. The problems considered are merging, sorting and selection. The size of the input is fixed at n, and the mesh size is varied from /spl radic/n/spl times//spl radic/n to n/spl times/n. The merging algorithm is optimal for all the mesh sizes, whereas the sorting and selection algorithms are within factors of i/(1-/spl epsiv/) and log/sup 4/3/ n respectively, of the optimal.>