TY - JOUR
T1 - Probabilistic integer sorting
AU - Gerbessiotis, Alexandros V.
AU - Siniolakis, Constantinos J.
N1 - Funding Information:
✩ This work was initiated at the Oxford University Computing Laboratory, Oxford, UK. An extended abstract appeared in the Workshop on Randomized Algorithms in Sequential Parallel and Distributed Computing (RALCOM’97), Greece, October 1997. The work of the first author was supported in part by EPSRC under grant GR/K16999 and of the second by a Bodossaki Foundation Graduate Scholarship. The experimental work of the first author was supported in part by NJIT SBR grant 421350 and NSF MRI-9977508. * Corresponding author. E-mail address: [email protected] (A.V. Gerbessiotis).
PY - 2004/5/31
Y1 - 2004/5/31
N2 - We introduce a probabilistic sequential algorithm for stable sorting n uniformly distributed keys in an arbitrary range. The algorithm runs in linear time and sorts all but a very small fraction 2-Ω(n) of the input sequences; the best previously known bound was 2 -Ω(n/(lgnlglgn)). An EREW PRAM extension of this sequential algorithm sorts in O((n/p+lgp)lgn/lg(n/p+lgn)) time using p≤n processors under the same probabilistic conditions. For a CRCW PRAM we improve upon the probabilistic bound of 2-Ω(n/(lgnlglgn)) obtained by Rajasekaran and Sen to derive a 2-Ω(nlglgn/lgn) bound. Additionally, we present experimental results for the sequential algorithm that establish the practicality of our method.
AB - We introduce a probabilistic sequential algorithm for stable sorting n uniformly distributed keys in an arbitrary range. The algorithm runs in linear time and sorts all but a very small fraction 2-Ω(n) of the input sequences; the best previously known bound was 2 -Ω(n/(lgnlglgn)). An EREW PRAM extension of this sequential algorithm sorts in O((n/p+lgp)lgn/lg(n/p+lgn)) time using p≤n processors under the same probabilistic conditions. For a CRCW PRAM we improve upon the probabilistic bound of 2-Ω(n/(lgnlglgn)) obtained by Rajasekaran and Sen to derive a 2-Ω(nlglgn/lgn) bound. Additionally, we present experimental results for the sequential algorithm that establish the practicality of our method.
KW - Analysis of algorithms
KW - Integer sorting
KW - Sorting uniform keys
UR - http://www.scopus.com/inward/record.url?scp=1842636097&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=1842636097&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2004.02.007
DO - 10.1016/j.ipl.2004.02.007
M3 - Article
AN - SCOPUS:1842636097
SN - 0020-0190
VL - 90
SP - 187
EP - 193
JO - Information Processing Letters
JF - Information Processing Letters
IS - 4
ER -