The Design and Analysis of BucketSort for Bubble Memory Secondary Storage

1 March 1985

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. C-34 (3) , 218-233
https://doi.org/10.1109/tc.1985.1676565

Abstract

BucketSort is a new external sorting algorithm for very large files that is a substantial improvement over merge sorting with disks. BucketSort requires an associative secondary storage device, which can be realized by large disk drives with logic-per-track capabilities or by magnetic bubble memory (MBM). This paper describes and analyzes a hypothetical Bucket-Sort implementation that uses bubble memory. A new software marking technique is introduced that reduces the effective time for an associative search.

Keywords

This publication has 7 references indexed in Scilit:

An Adaptive Method for Unknown Distributions in Distributive Partitioned Sorting
IEEE Transactions on Computers, 1985
Faster methods for random sampling
Communications of the ACM, 1984
Magnetic Bubble Memory Architectures for Supporting Associative Searching of Relational Databases
IEEE Transactions on Computers, 1980
A relational database machine architecture
Published by Association for Computing Machinery (ACM) ,1980
Associative-Search Bubble Devices for Content-Addressable Memory and Array Logic
IEEE Transactions on Computers, 1979
A dichromatic framework for balanced trees
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1978
Statistics of Extremes
Published by Columbia University Press ,1958