notes void msort(int []int nint int [] while( nmpass(xyln) mpass(yxln) the merging of two sub-liststhe first running from the index to mand the second running from the index ( + to requires no more than ( - + iterations hence if then no more than iterationswhere is the size of the list to be sorted therefore if is the size of the list to be sortedevery pass that merge routine performs requires time proportional to ( )and since the number of passes required to be performed are log the time complexity of the algorithm is (nlog ( ))both average and worst case the merge sort requires an additional list of size multi-way merge sort the two-phasemultiway merge-sort algorithm is similar to the external-memory merge-sort algorithm presented in the previous section phase is the samebutin phase the main loop is performed only once merging all [ /mruns into one run in one go to achieve thismultiway merging is performed instead of using the twoway-merge algorithm the idea of multiway merging is the same as for the two-way mergingbut instead of having input buffers (bf and bf of elementswe have [ /minput bufferseach elements long each buffer corresponds to one unfinished (or activerun initiallyall runs are active each buffer has pointer to the first unchosen element in that buffer (analogous to and in twowaymergethe multiway merging is performed by repeating these steps find the smallest element among the unchosen elements of all the input buffers linear search is sufficientbut if the cpu cost is also importantminimum priority queue can be used to store pointers to all the unchosen elements in input buffers in such casefinding the smallest element is logarithmic in the number of the active runs move the smallest element to the first available position of the output buffer if the output buffer is fullwrite it to the disk and reinitialize the buffer to hold the next output page if the bufferfrom which the smallest element was just taken is now exhausted of elementsread the next page from the corresponding run if no pages remain in that runconsider the run finished (no longer activelovely professional university