阿洛克·阿加瓦尔，杰弗里，S。维特
ACM通信，1988年9月，第31卷第9期，第1116-1127页
10.1145/48529.48535
评论
我们为内部存储器和二级存储器之间的输入和输出(I/OS)的数量提供了严格的上界和下界，直到一个常数因子，这是五个排序相关问题所需的:排序、快速傅立叶变换(FFT)、排列网络、排列和矩阵转置。边界在最坏情况和平均情况下都成立，在一些情况下常数因子匹配。二级存储被建模为一个磁盘，它能够在一个时间单位中传输P个块，每个块包含B个记录;每个块中的记录必须从磁盘上的B个连续位置输入或输出。针对该问题，我们给出了两种最优算法，分别是归并排序和分布排序的变体。特别地，我们证明了对于P = 1，标准归并排序算法是一种最优的外部排序方法，取决于I/ o数量的恒定因素。我们的排序算法使用与键排序的排列阶段相同的I/ o数，除非内部内存大小非常小，因此肯定了流行的格言:键排序并不更快。对于特殊情况B = P = O(1)，我们还给出了Hong and Kung的FFT下界的更简单和更直接的推导。
本文的全文是优质内容
没有发现记录
登录阅读全文
需要访问吗?
请选择下面的一个选项以访问高级内容和功能。
创建一个网上帐户
如果你已经是ACM会员，通信订阅者或数码图书馆订阅者，请设置网页帐户，以浏览本网站的优质内容。
参加ACM
成为ACM的会员，可以充分利用ACM卓越的计算信息资源、网络机会等优势。
订阅ACM杂志通讯
获得50多年的中华中医药学会内容的完整访问权限，并每月获得杂志印刷版。
购买这篇文章
非会员可以购买这篇文章或刊登这篇文章的杂志。
