simple approaches to external sorting if your operating system supports virtual memorythe simplest "externalsort is to read the entire file into virtual memory and run an internal sorting method such as quicksort this approach allows the virtual memory manager to use its normal buffer pool mechanism to control disk accesses unfortunatelythis might not always be viable option one potential drawback is that the size of virtual memory is usually limited to something much smaller than the disk space available thusyour input file might not fit into virtual memory limited virtual memory can be overcome by adapting an internal sorting method to make use of your own buffer pool more general problem with adapting an internal sorting algorithm to external sorting is that it is not likely to be as efficient as designing new algorithm with the specific goal of minimizing disk fetches consider the simple adaptation of quicksort to use buffer pool quicksort begins by processing the entire array of recordswith the first partition step moving indices inward from the two ends this can be implemented efficiently using buffer pool howeverthe next step is to process each of the subarraysfollowed by processing of sub-subarraysand so on as the subarrays get smallerprocessing quickly approaches random access to the disk drive even with maximum use of the buffer poolquicksort still must read and write each record log times on average we can do much better finallyeven if the virtual memory manager can give good performance using standard quicksortthis will come at the cost of using lot of the system' working memorywhich will mean that the system cannot use this space for other work better methods can save time while also using less memory our approach to external sorting is derived from the mergesort algorithm the simplest form of external mergesort performs series of sequential passes over the recordsmerging larger and larger sublists on each pass the first pass merges sublists of size into sublists of size the second pass merges the sublists of size into sublists of size and so on sorted sublist is called run thuseach pass is merging pairs of runs to form longer runs each pass copies the contents of the file to another file here is sketch of the algorithmas illustrated by figure split the original file into two equal-sized run files read one block from each run file into input buffers take the first record from each input bufferand write run of length two to an output buffer in sorted order take the next record from each input bufferand write run of length two to second output buffer in sorted order