Skip Navigation

The Computer Journal 1984 27(4):334-339; doi:10.1093/comjnl/27.4.334
© 1984 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (1)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Dobosiewicz, W.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Replacement Selection in 3-level Memories

W. Dobosiewicz *

Department of Computing and Information Science, University of Guelph, Guelph, Ontario, Canada

External merge sorting consists of two phases; the formation of initial runs and the merge of the runs into a sorted file (possible in several merge passes). The replacement selection algorithm is typically used to create initial runs. It employs two levels of memory: main memory and a sequential accessed tape-like memory. Natural selection uses a third memory level to increase the average length of an initial run. Although natural selection produces longer runs than replacement selection, it is not competitive because the added overhead is excessive. This paper discusses two other methods of creating longer initial runs in a 3-level memory. Their efficiency is higher than that of natural selection and they also outperform a 3-level replacement selection in most circumstances. The second algorithm has the additional feature that it allows the auxiliary memory to be broken into several smaller parts, thus increasing the average run length. As most computer systems have rotating mass storage, this property is of practical value.

Received August 1983.

* On leave from the University of Warsaw, Warsaw, Poland.

§ Department of Computing and Information Science, University of Guelph, Guelph, Ontario, Canada N1G 2W1


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.