written back to disk this continues until all pairs of blocks have been merged next each pair of -block sequences is merged into -block sequence each time the size of the sorted sequences doublesuntil the entire file is sorted figure shows the mergesort process on an external file the file consists of four blocks of four records eachfor total of records only three blocks can fit in internal memory (of course all these sizes would be much larger in real situation figure - shows the file before sortingthe number in each record is its key value figure mergesort on an external file internal sort of blocks in the first phase all the blocks in the file are sorted internally this is done by reading the block into memory and sorting it with any appropriate internal sorting algorithmsuch as quicksort (or for smaller numbers of recordsshellsort or insertion sortthe result of sorting the blocks internally is shown in figure - the dotted lines in the figure separate sorted recordssolid lines separate unsorted records second file may be used to hold the sorted blocksand we assume that availability of external storage is not problem it' often desirable to avoid modifying the original file merging in the second phase we want to merge the sorted blocks in the first pass we merge every pair of blocks into sorted -block sequence thus the two blocks - and - are merged into -- - also- and - are merged into -- - the result is shown in figure - third file is necessary to hold the result of this merge step in the second passthe two -record sequences are merged into -record sequenceand the sort is complete of course more merge steps would be required to sort larger filesthe number of such steps is proportional to log the merge steps can alternate between two files internal arrays because the computer' internal memory has room for only three blocksthe merging process must take place in stages let' say there are three arrayscalled arr arr and arr each of which can hold block