3.8 EXTERNAL POLYPHASE MERGE SORT 97sorted list between file A and file B. An algorithm to accomplish this first step
would be
CreateRuns( S )
S is the size of the runs to be created
CurrentFile = A
while not at the end of the input file do
read S records from the input file
sort the S records
write the records to file CurrentFile
if CurrentFile = A then
CurrentFile = B
else
CurrentFile = A
end if
end while
Once we have processed the entire original file into sorted runs, we are now
ready to start the second step, which is to merge these runs. If you think about
the process, you will realize that both files A and B have some number of runs
ofS records that are in order. But, as in merge sort, we can’t really say anything
about the relationship between the records that are in two separate runs.
Our merging process will be similar to the MergeLists function of Sec-
tion 3.6, however, in this case, instead of moving the records to a new array, we
will move them to a new file. So we begin by reading in half of the first runs
from files A and B. We can only read in half of each run because we have
already identified that we can only hold S records at a time, and we need
records from both files A and B. We now begin to merge them into a new file
C. If we run through the first half of records from either file, we will then read
in the second set of records for this run. When we have completed one of the
two runs, the rest of the other run is written to the file. Once the first runs of
files A and B have been merged, we then merge the second two runs, but this
time the output is written to file D. This process continues to merge runs and
write them alternately to files C and D. On the completion of this pass, you
should see that we now have runs of 2S records in files C and D. We repeat the
process again, but this time we read runs from C and D and write them to files
A and B, which will then have runs with 4S records. You should see that even-
tually we will have merged the runs into one list that is now sorted. An algo-
rithm to accomplish this second step would be