Improved sorting networks withO(logN) depth |
| |
Authors: | M. S. Paterson |
| |
Affiliation: | (1) Department of Computer Science, University of Warwick, CV4 7AL Coventry, England |
| |
Abstract: | The sorting network described by Ajtaiet al. was the first to achieve a depth ofO(logn). The networks introduced here are simplifications and improvements based strongly on their work. While the constants obtained for the depth bound still prevent the construction being of practical value, the structure of the presentation offers a convenient basis for further development.The author was supported by a Senior Fellowship from the Science and Engineering Research Council during the course of this work. |
| |
Keywords: | Sorting networks Comparators Parallel algorithm |
本文献已被 SpringerLink 等数据库收录! |