Title :
Sorting n objects with a k-sorter
Author :
Beigel, Richard ; Gill, John
Author_Institution :
Dept. of Comput. Sci., Johns Hopkins Univ., Baltimore, MD, USA
fDate :
5/1/1990 12:00:00 AM
Abstract :
A k-sorter is a device that sorts k objects in unit time. The complexity of an algorithm that uses a k-sorter is defined 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 4n log n/k log k, up to first-order terms in n and k
Keywords :
computational complexity; sorting; algorithm; complexity; k-sorter; n objects sorting; Application software; Computer aided software engineering; Computer science; Coprocessors; Costs; Floors; Hardware; Sorting; Upper bound;
Journal_Title :
Computers, IEEE Transactions on
