An improved reliability bound of a probabilistic parallel integer sorting algorithm

作者：Gerbessiotis Alexandros V^*

来源：Information Processing Letters, 2012, 112(24): 976-979.

DOI：10.1016/j.ipl.2012.09.003

• Analysis of algorithms
• Parallel algorithms
• Randomized algorithms
• Uniformly distributed integers
• Integer sorting

It is shown how one can improve the reliability bound of the parallel sorting algorithm of Rajasekaran and Sen (1992) 171 that sorts uniformly distributed integer keys on a CRCW Parallel Random Access Machine (PRAM). The probability of success improves to -%26gt; 2-(Omega(n log log n/ logn)) from the previous bound of 1 - 2(-Omega(n/logn log logn))) while retaining the (O) over tilde (logn) time bound for sorting n uniformly distributed integers on n/logn processors.

• 出版日期2012-12-31