chap file processing and external sorting merge the runs together to form single sorted file replacement selection this section treats the problem of creating initial runs as large as possible from disk fileassuming fixed amount of ram is available for processing as mentioned previouslya simple approach is to allocate as much ram as possible to large arrayfill this array from diskand sort the array using quicksort thusif the size of memory available for the array is recordsthen the input file can be broken into initial runs of length better approach is to use an algorithm called replacement selection thaton averagecreates runs of records in length replacement selection is actually slight variation on the heapsort algorithm the fact that heapsort is slower than quicksort is irrelevant in this context because / time will dominate the total running time of any reasonable external sorting algorithm building longer initial runs will reduce the total / time required replacement selection views ram as consisting of an array of size in addition to an input buffer and an output buffer (additional / buffers might be desirable if the operating system supports double bufferingbecause replacement selection does sequential processing on both its input and its output imagine that the input and output files are streams of records replacement selection takes the next record in sequential order from the input stream when neededand outputs runs one record at time to the output stream buffering is used so that disk / is performed one block at time block of records is initially read and held in the input buffer replacement selection removes records from the input buffer one at time until the buffer is empty at this point the next block of records is read in output to buffer is similaronce the buffer fills up it is written to disk as unit this process is illustrated by figure replacement selection works as follows assume that the main processing is done in an array of size records fill the array from disk set last build min-heap (recall that min-heap is defined such that the record at each node has key value less than the key values of its children repeat until the array is empty(asend the record with the minimum key value (the rootto the output buffer (blet be the next record in the input buffer if ' key value is greater than the key value just output then place at the root