quentially and write the output run files sequentially for sequential processing and double buffering to be effectivehoweverit is necessary that there be separate / head available for each file this typically means that each of the input and output files must be on separate disk drivesrequiring total of four disk drives for maximum efficiency the external mergesort algorithm just described requires that log passes be made to sort file of records thuseach record must be read from disk and written to disk log times the number of passes can be significantly reduced by observing that it is not necessary to use mergesort on small runs simple modification is to read in block of datasort it in memory (perhaps using quicksort)and then output it as single sorted run example assume that we have blocks of size kband records are eight bytes with four bytes of data and -byte key thuseach block contains records standard mergesort would require nine passes to generate runs of recordswhereas processing each block as unit can be done in one pass with an internal sort these runs can then be merged by mergesort standard mergesort requires eighteen passes to process records using an internal sort to create initial runs of records reduces this to one initial pass to create the runs and nine merge passes to put them all togetherapproximately half as many passes we can extend this concept to improve performance even further available main memory is usually much more than one block in size if we process larger initial runsthen the number of passes required by mergesort is further reduced for examplemost modern computers can provide tens or even hundreds of megabytes of ram to the sorting program if all of this memory (excepting small amount for buffers and local variablesis devoted to building initial runs as large as possiblethen quite large files can be processed in few passes the next section presents technique for producing large runstypically twice as large as could fit directly into main memory another way to reduce the number of passes required is to increase the number of runs that are merged together during each pass while the standard mergesort algorithm merges two runs at timethere is no reason why merging needs to be limited in this way section discusses the technique of multiway merging over the yearsmany variants on external sorting have been presentedbut all are based on the following two steps break the file into large initial runs