Abstract
It is shown how one can improve the reliability bound of the parallel sorting algorithm of Rajasekaran and Sen (1992) [7] that sorts uniformly distributed integer keys on a CRCW Parallel Random Access Machine (PRAM). The probability of success improves to 1-2 -Ω(nloglogn/logn) from the previous bound of 1-2 -Ω(n/(lognloglogn)) while retaining the Õ(logn) time bound for sorting n uniformly distributed integers on n/logn processors.
Original language | English (US) |
---|---|
Pages (from-to) | 976-979 |
Number of pages | 4 |
Journal | Information Processing Letters |
Volume | 112 |
Issue number | 24 |
DOIs | |
State | Published - Dec 31 2012 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications
Keywords
- Analysis of algorithms
- Integer sorting
- Parallel algorithms
- Randomized algorithms
- Uniformly distributed integers