load first page of relation R in the input frame F1
load next M-2 pages of R in the buffer
set Q1 = queue of records in the M-2 frames starting from F2
set Q2 = empty queue
while (F1 or Q1 or Q2 are not empty):
if (Q1 is empty):
move Q2 into Q1
if (output frame is not empty):
write output frame in secondary storage
create new run
find minimum record r1 in Q1
move r1 in the output frame
if (F1 is empty and R has more pages):
read next page from R
if (F1 is NOT empty):
point to the next record r2 in input frame F1
if (r1 < r2):
move r2 in Q1
else:
move r2 in Q2
if (output frame is full):
write output frame in secondary storage
set i = 1
while (there are other runs to consider for pass i):
select M-1 runs created in pass i-1 and not yet analyzed
load first page of each run in the buffer
set pointer of each frame to first record of each page
while (buffer is not empty):
find minimum record r among pointed records
write the minimum record r in the output frame
if (record r was NOT last of its frame):
point to next record for corresponding frame
else if (corresponding run has more pages):
load next page of record r's run to the frame
set pointer of the frame to its first record
if (output frame is full):
write output frame in secondary storage
if (we are at last record of last page for each run):
set i = i+1