Replacement Selection unlike other #202203102010, is aimed to produce optimised runs instead of handling the sorting entirely.
It needs at least two structures: a 202202062259 which is used to compare the items in the tape or drive and an array which is used to store any items that is smaller than the latest inserted item.
First, we will build a heap by using the first \(M\) items in the input tape or drive. After that, we will write the smallest item in the heap to the output tape or drive where later it will be deleted from the heap, and then compare it to the current first item in the input tape or drive to determine whether it is larger than the latest inserted item. If it is indeed larger, it will be added into the heap. Otherwise, it will go to the array. The steps will be done recursively until either it hit the end of the tape or the array becomes full.
When the array becomes full, the items of the array will be used to construct a new heap. Repeat the steps above until there is no items left in the input tape.
This algorithm is best when combined with one of the #202203102010 to achieve greater performance compare to naive merges.