chap file processing and external sorting runs of length runs of length runs of length figure simple external mergesort algorithm input records are divided equally between two input files the first runs from each input file are merged and placed into the first output file the second runs from each input file are merged and placed in the second output file merging alternates between the two output files until the input files are empty the roles of input and output files are then reversedallowing the runlength to be doubled with each pass repeat until finishedalternating output between the two output run buffers whenever the end of an input block is reachedread the next block from the appropriate input file when an output buffer is fullwrite it to the appropriate output file repeat steps through using the original output files as input files on the second passthe first two records of each input run file are already in sorted order thusthese two runs may be merged and output as single run of four elements each pass through the run files provides larger and larger runs until only one run remains example using the input of figure we first create runs of length one split between two input files we then process these two input files sequentiallymaking runs of length two the first run has the values and which are output to the first output file the next run has and which is output to the second file the run is sent to the first filethen run is sent to the second fileand so on once this pass has completedthe roles of the input files and output files are reversed the next pass will merge runs of length two into runs of length four runs and are merged to send to the first output file then runs and are merged to send run to the second output file in the final passthese runs are merged to form the final run this algorithm can easily take advantage of the double buffering techniques described in section note that the various passes read the input run files se