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 numbers. All available space is used for storing records, resulting in a larger tree, 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 exploited 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.
replacement selection sorting algorithms data structures