if ~ eof then copyrun( end until eofruns set( )runs set( ) :files new("")files set( )(*merge from and to * : repeat repeat if first first then runs copy( )if eor then copyrun( end else runs copy( )if eor then copyrun( end end until eor eorinc(luntil eof or eofwhile ~ eof do copyrun( )inc(lendwhile ~ eof do copyrun( )inc(lendruns set( until return end naturalmergebalanced multiway merging the effort involved in sequential sort is proportional to the number of required passes sinceby definitionevery pass involves the copying of the entire set of data one way to reduce this number is to distribute runs onto more than two files merging runs that are equally distributed on files results in sequence of / runs second pass reduces their number to / third pass to / and after passes there are /nk runs left the total number of passes required to sort items by -way merging is therefore logn(nsince each pass requires copy operationsthe total number of copy operations is in the worst case logn(nas the next programming exercisewe will develop sort program based on multiway merging in order to further contrast the program from the previous natural two-phase merging procedurewe shall formulate the multiway merge as single phasebalanced mergesort this implies that in each pass there are an equal number of input and output files onto which consecutive runs are alternately distributed using filesthe algorithm will therefore be based on -way merging following the previously adopted strategywe will not bother to detect the automatic merging of two consecutive runs distributed onto the same file consequentlywe are forced to design the merge program whithout assuming strictly equal numbers of runs on the input files in this program we encounter for the first time natural application of data structure consisting of arrays of files as matter of factit is surprising how strongly the following program differs from the previous one because of the change from two-way to multiway merging the change is primarily result of the circumstance that the merge process can no longer simply be terminated after one of the input runs is exhausted insteada list of inputs that are still activei not yet exhaustedmust be kept another complication stems from the need to switch the groups of input and output files after each pass here the indirection of access to files via riders comes in handy in each passdata may be copied from the same riders to the same riders at the end of each pass we merely need to reset the input and output files to