DETERMINISTIC SORTING IN NEARLY LOGARITHMIC TIME ON THE HYPERCUBE AND RELATED COMPUTERS

被引：18

作者：

CYPHER, R

PLAXTON, CG

机构：

[1] UNIV TEXAS,DEPT COMP SCI,AUSTIN,TX 78712

[2] MIT,COMP SCI LAB,CAMBRIDGE,MA 02139

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 1993年 / 47卷 / 03期

基金：

加拿大自然科学与工程研究理事会;

关键词：

D O I：

10.1016/0022-0000(93)90043-V

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper presents a deterministic sorting algorithm, called Sharesort, that sorts n records on an n-processor hypercube, shuffle-exchange, or cube-connected cycles in O(log n(log log n)2) time in the worst case. The algorithm requires only a constant amount of storage at each processor. The fastest previous deterministic algorithm for this problem was Batcher's bitonic sort, which runs in O(log2 n) time. © 1993.

引用

页码：501 / 548

页数：48

共 18 条

[1] SORTING IN C LOG N PARALLEL STEPS [J].