Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
复制标题
最优和次对数时间随机并行排序算法
DOI：
--
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
J. Reif
中科院分区：
文献类型：
--
作者：
S. Rajasekaran;J. Reif
本文假设了一个允许全局存储器并发读写的并行随机存取机（RAM）模型，主要结果是整数SORT的一个最优随机并行算法（即，对于在范围$[1，n]$中排序n个整数）。该算法仅花费对数时间，并且是第一个已知的最优算法：其时间和处理器边界的乘积的上界是输入大小的线性函数。给出了前缀和的确定性亚对数时间算法。此外，本文还提出了一种并行获得n个元素随机排列的亚对数时间算法。最后给出了GENERAL_SORT和INTEGER_SORT的亚对数时间算法。我们的次对数GENERAL_SORT算法也是最优的。
This paper assumes a parallel RAM (random access machine) model which allows both concurrent reads and concurrent writes of a global memory.The main result is an optimal randomized parallel algorithm for INTEGER_SORT (i.e., for sorting n integers in the range $[1,n]$). This algorithm costs only logarithmic time and is the first known that is optimal: the product of its time and processor bounds is upper bounded by a linear function of the input size. Also given is a deterministic sublogarithmic time algorithm for prefix sum. In addition this paper presents a sublogarithmic time algorithm for obtaining a random permutation of n elements in parallel. And finally, sublogarithmic time algorithms for GENERAL_SORT and INTEGER_SORT are presented. Our sub-logarithmic GENERAL_SORT algorithm is also optimal.