Replacement Selection in 3-level Memories

Open Access
Publisher Website
Google Scholar
Abstract
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.

This publication has 0 references indexed in Scilit: