SORTING N-OBJECTS WITH A K-SORTER

被引：14

作者：

BEIGEL, R

GILL, J

机构：

[1] JOHNS HOPKINS UNIV,DEPT COMP SCI,BALTIMORE,MD 21218

[2] STANFORD UNIV,DEPT COMP SCI,STANFORD,CA 94305

来源：

IEEE TRANSACTIONS ON COMPUTERS | 1990年 / 39卷 / 05期

基金：

美国国家科学基金会;

关键词：

Coprocessor; it-sorter; percentile sort; selection; sorting; tournament-merge sort;

D O I：

10.1109/12.53587

中图分类号：

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

学科分类号：

0812 ;

摘要：

A k-sorter is a device that sorts k objects in unit time. We define the complexity of an algorithm that uses a k-sorter as the number of applications of the k-sorter. In this measure, the complexity of sorting n objects is between n log n/k log k and in log n/k log k, up to first order terms in n and k. © 1990 IEEE

引用

页码：714 / 716

页数：3