replaces several (potentiallysequential passes with single random access pass if the processing would not be sequential anyway (such as when all processing is on single disk drive)no time is lost by doing so multiway merging can greatly reduce the number of passes required if there is room in memory to store one block for each runthen all runs can be merged in single pass thusreplacement selection can build initial runs in one passand multiway merging can merge all runs in one passyielding total cost of two passes howeverfor truly large filesthere might be too many runs for each to get block in memory if there is room to allocate blocks for -way mergeand the number of runs is greater than bthen it will be necessary to do multiple merge passes in other wordsthe first runs are mergedthen the next band so on these super-runs are then merged by subsequent passesb super-runs at time how big file can be merged in one passassuming blocks were allocated to the heap for replacement selection (resulting in runs of average length blocks)followed by -way mergewe can process on average file of size blocks in single multiway merge + blocks on average can be processed in bway merges to gain some appreciation for how quickly this growsassume that we have available mb of working memoryand that block is kbyielding blocks in working memory the average run size is mb (twice the working memory sizein one pass runs can be merged thusa file of size mb canon averagebe processed in two passes (one to build the runsone to do the mergewith only mb of working memory larger block size would reduce the size of the file that can be processed in one merge pass for fixed-size working memorya smaller block size or larger working memory would increase the file size that can be processed in one merge pass with mb of working memory and kb blocksa file of size gigabytes could be processed in two merge passeswhich is big enough for most applications thusthis is very effective algorithm for single disk drive external sorting figure shows comparison of the running time to sort various-sized files for the following implementations( standard mergesort with two input runs and two output runs( two-way mergesort with large initial runs (limited by the size of available memory)and ( -way mergesort performed after generating large initial runs in each casethe file was composed of series of four-byte records ( two-byte key and two-byte data value)or records per megabyte of file size we can see from this table that using even modest memory size (two blocksto create initial runs results in tremendous savings in time doing -way merges of the runs provides another considerable speeduphowever large-scale multi-way