sorting runs and the other tapes are empty we must copy one run to another tapeand then we can finish the merge it turns out that the first distribution we gave is optimal if the number of runs is fibonacci number fn then the best way to distribute them is to split them into two fibonacci numbers fn- and fn- otherwiseit is necessary to pad the tape with dummy runs in order to get the number of runs up to fibonacci number we leave the details of how to place the initial set of runs on the tapes as an exercise we can extend this to -way mergein which case we need kth order fibonacci numbers for the distributionwhere the kth order fibonacci number is defined as ( (nf( ( ( ( ( ( )with the appropriate initial conditions ( ( < < ( ( replacement selection the last item we will consider is construction of the runs the strategy we have used so far is the simplest possiblewe read as many records as possible and sort themwriting the result to some tape this seems like the best approach possibleuntil one realizes that as soon as the first record is written to an output tapethe memory it used becomes available for another record if the next record on the input tape is larger than the record we have just outputthen it can be included in the run using this observationwe can give an algorithm for producing runs this technique is commonly referred to as replacement selection initiallym records are read into memory and placed in priority queue we perform deleteminwriting the smallest (valuedrecord to the output tape we read the next record from the input tape if it is larger than the record we have just writtenwe can add it to the priority queue otherwiseit cannot go into the current run since the priority queue is smaller by one elementwe can store this new element in the dead space of the priority queue until the run is completed and use the element for the next run storing an element in the dead space is similar to what is done in heapsort we continue doing this until the size of the priority queue is zeroat which point the run is over we start new run by building new priority queueusing all the elements in the dead space figure shows the run construction for the small example we have been usingwith dead elements are indicated by an asterisk in this examplereplacement selection produces only three runscompared with the five runs obtained by sorting because of thisa three-way merge finishes in one pass instead of two if the input is randomly distributedreplacement selection can be shown to produce runs of average length for our large examplewe would expect runs instead of runsso five-way merge would require four passes in this casewe have not saved passalthough we might if we get lucky and have runs or less since external sorts take so longevery pass saved can make significant difference in the running time as we have seenit is possible for replacement selection to do no better than the standard algorithm howeverthe input is frequently sorted or nearly sorted to start within which case replacement selection produces only few very long runs this kind of input is common for external sorts and makes replacement selection extremely valuable