98 SORTING ALGORITHMS
PolyphaseMerge( S )
S is the size of the initial runs
Size = S
Input1 = A
Input2 = B
CurrentOutput = C
while not done do
while more runs this pass do
Merge one run of length Size from file Input1
with one run of length Size from file Input2
sending output to CurrentOutput
if (CurrentOutput = A) then
CurrentOutput = B
elseif (CurrentOutput = B) then
CurrentOutput = A
elseif (CurrentOutput = C) then
CurrentOutput = D
elseif (CurrentOutput = D) then
CurrentOutput = C
end if
end while
Size = Size * 2
if (Input1 = A) then
Input1 = C
Input2 = D
CurrrentOutput = A
else
Input1 = A
Input2 = B
CurrentOutput = C
end if
end while
Before we begin our analysis, we first look at what we have in terms of runs
and the number of passes this translates to. If we have N records in our original
file, and we can store S records at one time, this means that after CreateRuns
we must have R = N / S runs split between the two files. Each of the
PolyphaseMerge passes joins pairs of runs, so it must cut the number of runs
in half. After one pass there will be R / 2 runs, after two passes there will be
R / 4 runs, and, in general, after j passes there will be R / 2j runs. Because
we stop when we get down to one run, this will be when R / 2D is equal to
1, which will be when D is lgR. This means we will do lgR passes of the
merge process.