AN OPTIMAL PARALLEL ALGORITHM FOR SORTING MULTISETS

Authors
RAJASEKARAN S
Citation
S. Rajasekaran, AN OPTIMAL PARALLEL ALGORITHM FOR SORTING MULTISETS, Information processing letters, 67(3), 1998, pp. 141-143
Citations number
7
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
67
Issue
3
Year of publication
1998
Pages
141 - 143
Database
ISI
SICI code
0020-0190(1998)67:3<141:AOPAFS>2.0.ZU;2-T
Abstract
We consider the problem of sorting n numbers that contain only k disti nct values. We present a randomized arbitrary CRCW PRAM algorithm that runs in O(log n) time using (n log k)/log n processors. The same algo rithm runs in O((log n)/log log n) time with a total work of O(n (log k)(1+epsilon)) for any fixed epsilon > 0. All the stated bounds hold w ith high probability. (C) 1998 Published by Elsevier Science B.V. All rights reserved.