multiway merging in standard merge-sort (section )the merge process combines two sorted sequences into one by repeatedly taking the smaller of the items at the front of the two respective lists in -way mergewe repeatedly find the smallest among the items at the front of the sequences and place it as the next element of the merged sequence we continue until all elements are included in the context of an external-memory sorting algorithmif main memory has size and each block has size bwe can store up to / blocks within main memory at any given time we specifically choose ( / so that we can afford to keep one block from each input sequence in main memory at any given timeand to have one additional block to use as buffer for the merged sequence (see figure figure -way merge with and blocks that currently reside in main memory are shaded we maintain the smallest unprocessed element from each input sequence in main memoryrequesting the next block from sequence when the preceding block has been exhausted similarlywe use one block of internal memory to buffer the merged sequenceflushing that block to external memory when full in this waythe total number of transfers performed during single -way merge is ( / )since we scan each block of list si onceand we write out each block of the merged list once in terms of computation timechoosing the smallest of values can trivially be performed using (doperations if we are willing to devote (dinternal memorywe can maintain priority queue identifying the smallest element from each sequencethereby performing each step of the merge in (log dtime by removing the minimum element and replacing it with the next element from the same sequence hencethe internal time for the -way merge is ( log dproposition given an array-based sequence of elements stored compactly in external memorywe can sort with (( /blog( / )log( / )block transfers and ( log ninternal computationswhere is the size of the internal memory and is the size of block