S.Q. Zheng, Dept. of Comput. Sci., Louisiana State Univ., Baton Rouge, LA, USA
B. Calidas, Dept. of Comput. Sci., Louisiana State Univ., Baton Rouge, LA, USA
Yanjung Zhang, Dept. of Comput. Sci., Louisiana State Univ., Baton Rouge, LA, USA
We present a simple and general parallel sorting scheme, ZZ-sort, which can be used to derive a class of efficient in-place sorting algorithms on realistic parallel machine models. We prove a tight bound for the worst case performance of ZZ-sort. We also demonstrate the average performance of ZZ-sort by experimental results obtained on a MasPar parallel computer. Our experiments indicate that ZZ-sort can be incorporated into a distributed memory parallel computer system as a standard routine, and this routine is useful for space critical situations. Finally, we show that ZZ-sort can be used to convert a non-adaptive parallel sorting algorithm into an in-place and adaptive one by considering the problem of sorting an arbitrarily large input on fixed-size reconfigurable meshes.
Index Terms:
sorting; parallel algorithms; distributed memory systems; reconfigurable architectures; safety-critical software; in-place sorting algorithms; feasible parallel machine models; parallel sorting scheme; ZZ-sort; tight bound; worst case performance; average performance; MasPar parallel computer; distributed memory parallel computer system; standard routine; space critical situations; parallel sorting algorithm; fixed-size reconfigurable meshes
Citation:
S.Q. Zheng, B. Calidas, Yanjung Zhang, "Efficient in-place sorting algorithms using feasible parallel machine models," ispan, pp.15, 1996 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '96), 1996
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb