zbMATH — the first resource for mathematics

Parallel sorting algorithms. (English) Zbl 0657.68070
Notes and Reports in Computer Science and Applied Mathematics, 12. Orlando etc.: Academic Press, Inc. (Harcourt Brace Jovanovich, Publishers). XIII, 229 p.; $ 26.00 (1985).
‘Parallel sorting algorithms’ is an overview over sorting algorithms for various parallel computer architectures. After introducing the problem of sorting, giving a taxonomy of parallel computer architectures and discussing efficiency concepts in parallel algorithms, various sorting methods on SIMD and MIMD computers are introduced. The author describes and analyzes sorting algorithms on sorting networks, vector machines, the perfect-shuffle, mesh- and cube-connected computers, tree machines and asynchronous MIMD machines. Furthermore, there are chapters on parallel external sorting and general lower bounds for the problem of parallel sorting.
The book is very readable and serves as an excellent means to get an overview over methods to solve the important problem of parallel sorting.
Reviewer: W.Janko

68P10 Searching and sorting
68-02 Research exposition (monographs, survey articles) pertaining to computer science
68N99 Theory of software