when only one active run remains the algorithm finishes up as shown in lines and of twoway-merge-it just copies all the remaining elements to the end of file figure visualizes multiway merging notes figure main-memory organization for multiway merging input buffersone for each unfinished run select smallest unchosen element for output bf pointers to first unchosen elements it is easy to see that phase of the two-phasemultiway merge-sort algorithm performs only th (ni/ operations and this is also the running time of the whole algorithm in spite of thisthe algorithm has limitation-it can not sort very large files if phase of the algorithm produces more than runs ( / )all runs can not be merged in one go in phase because each run requires one-page input buffer in main-memory and one page of main-memory is reserved for the output buffer how large should the file be for this to happenmultiway merge sort of very large files sometimes there may be need to sort extremely large files or there is only small amount of available main memory as described in the previous sectiontwo-phasemultiway merge sort may not work in such situations natural way to extend the two-phasemultiway merge sort for files of any size is to do not one but many iterations in phase of the algorithm that iswe employ the external memory merge-sort algorithm from section but instead of using twoway-mergewe use the multiway merging (as described in the previous sectionto merge runs from file into one run in file thenin each iteration of the main loop of phase we reduce the number of runs by factor of what is the running time of this algorithmwhich we call simply multiway merge sort phase and each iteration of the main loop of phase takes th(ni/ operations after phase we start up with [ / [ /mrunseach iteration of the main loop of phase reduces the number of runs by factor of and we stop when we have just one run thusthere are logm- ( /miterations of the main loop of phase thereforethe total running time of the algorithm is th( logm- ( / )th ( logm logmmth ( logm nth ( logm nremember that the cost of the external-memory merge-sort algorithm from section is th( log ( / )thusmultiway merge sort is faster by factor of ( /logmn)log mactuallylovely professional university