sec external sorting input file input buffer ram output buffer output run file figure overview of replacement selection input records are processed sequentially initially ram is filled with records as records are processedthey are written to an output buffer when this buffer becomes fullit is written to disk meanwhileas replacement selection needs recordsit reads them from the input buffer whenever this buffer becomes emptythe next block of records is read from disk ii else replace the root with the record in array position lastand place at position last set last last (csift down the root to reorder the heap when the test at step (bis successfula new record is added to the heapeventually to be output as part of the run as long as records coming from the input file have key values greater than the last key value output to the runthey can be safely added to the heap records with smaller key values cannot be output as part of the current run because they would not be in sorted order such values must be stored somewhere for future processing as part of another run howeverbecause the heap will shrink by one element in this casethere is now free space where the last element of the heap used to bethusreplacement selection will slowly shrink the heap and at the same time use the discarded heap space to store records for the next run once the first run is complete ( the heap becomes empty)the array will be filled with records ready to be processed for the second run figure illustrates part of run being created by replacement selection it should be clear that the minimum length of run will be records if the size of the heap is because at least those records originally in the heap will be part of the run under good conditions ( if the input is sorted)then an arbitrarily long run is possible in factthe entire file could be processed as one run if conditions are bad ( if the input is reverse sorted)then runs of only size result what is the expected length of run generated by replacement selectionit can be deduced from an analogy called the snowplow argument imagine that snowplow is going around circular track during heavybut steadysnowstorm after the plow has been around at least oncesnow on the track must be as follows immediately behind the plowthe track is empty because it was just plowed the greatest level of snow on the track is immediately in front of the plowbecause