Linear sorting withO(logn) processors |
| |
| Authors: | J A Orenstein T H Merrett L Devroye |
| |
| Institution: | (1) School of Computer Science, McGill University, 805 Sherbrooke Street West, H3A 2K6 Montréal, PQ, Canada;(2) Present address: COINS Department, University of Massachusetts, 01003 Amherst, MA, USA |
| |
| Abstract: | A file ofn records can be sorted in linear time givenO(log(n)) processors. Four such algorithms are presented and analyzed. All of them have reasonable hardware requirements; no memory access conflicts are generated; a constant number of communication lines per processor are needed (except for one case); and the space requirements areO(n) orO(n log(log(n))). |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
