chap file processing and external sorting file size sort , , , , sort memory size (in blocks , , , , , , , , , , , , sort memory size (in blocks , , , , , , , , , figure comparison of three external sorts on collection of small records for files of various sizes each entry in the table shows time in seconds and total number of blocks read and written by the program file sizes are in megabytes for the third sorting algorithmon file size of mbthe time and blocks shown in the last column are for -way merge is used instead of because is root of the number of blocks in the file (while is not)thus allowing the same number of runs to be merged at every pass merges for beyond about or runs does not help much because lot of time is spent determining which is the next smallest element among the runs we see from this experiment that building large initial runs reduces the running time to slightly more than one third that of standard mergesortdepending on file and memory sizes using multiway merge further cuts the time nearly in half in summarya good external sorting algorithm will seek to do the followingmake the initial runs as long as possible at all stagesoverlap inputprocessingand output as much as possible use as much working memory as possible applying more memory usually speeds processing in factmore memory will have greater effect than faster disk faster cpu is unlikely to yield much improvement in running time for external sortingbecause disk / speed is the limiting factor if possibleuse additional disk drives for more overlapping of processing with /oand to allow for sequential file processing further reading good general text on file processing is folk and zoellig' file structuresa conceptual toolkit [fz somewhat more advanced discussion on key issues in file processing is betty salzberg' file structuresan analytical approach [sal