A refinement of replacement selection

We present a refinement of replacement selection which eliminates the extra space requirements for storing two replacement trees or storing run number s. All available space is used for storing records, resulting in a larger t ree, longer runs, fewer runs, and reduced sorting time. The algorithm uses an "earlier than" operator for key comparison, which is a generalization of the "less than" operator, and which permits storing, in one tree, records in the current run and records in the next run. This operator is also explo ited to fill the tree initially, and to empty the tree after the input has been exhausted. (C) 1999 Elsevier Science B.V. All rights reserved.