Title :
The Design and Analysis of BucketSort for Bubble Memory Secondary Storage
Author :
Lindstrom, Eugene E. ; Vitter, Jeffrey Scott
Author_Institution :
IBM Palo Alto Scientific Center
fDate :
3/1/1985 12:00:00 AM
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 :
Analysis of algorithms; associative memory; database systems; external sorting; magnetic bubble memory; probabilistic algorithms; secondary storage; vector processing; Associative memory; Computer aided manufacturing; Database systems; Disk drives; Helium; Magnetic analysis; Magnetic devices; Packaging; Sorting; Vector processors; Analysis of algorithms; associative memory; database systems; external sorting; magnetic bubble memory; probabilistic algorithms; secondary storage; vector processing;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1985.1676565
