Return to Mr Belvedere's Programming Nook
Merge Sort
© 1996 by Bobby Griggs.
(**************************************************************************)
(* *)
(* Robert C. Griggs, Jr. *)
(* Program name - MERGSORT.P *)
(* October 17, 1991 *)
(* *)
(**************************************************************************)
(*
This program is designed to sort randomly generated integers in a binary
file in ascending order. The integers are not loaded into an array for
purposes of sorting, but are instead read from the file and compared to
the next integer to determine if the record needs to be sorted. Two
temporary files are used for the runs necessary to merge the integers.
An integer is read from the file and placed into the first temporary
file. On the basis of a comparison to the next integer, the run is
either completed or continued until the next integer is less than the
one currently being copied. Once conditions have been met to signal the
end or run boolean, the runs are merged back together in ascending order.
*)
(**************************************************************************)
(*
Algorithm:
1. Specify three constants for the filenames to be used in the program.
NUMSORT for the input file called sortnums.dat
TEMP1 for the temporary file for the first run
TEMP2 for the temporary file for the second run
2. Specify a type statement to define the file types to be used in the
program.
nums - file of integer for the binary file that contains the
randomly generated numbers
3. Specify variables for use within program.
sortfile of type nums for input file of integers
tmp1 of type nums for the first temporary file for a sort run
tmp2 of type nums for the second temporary file for a sort run
4. Run procedure naturalmerge to sort the file.
A. use the following variables:
l for tracking the numbers of runs done on a pass through
the file. When this variable equals 1 the sort is
completed.
eor for determining whether the conditions for the end of
a run has been met
B. rewrite the first and second temporary files
C. reset the input file to read in the integers
D. run nested procedure distribute to distribute the integers
into runs
1. run nested procedure copyrun using sortfile and temporary
file number 1 to run procedure copy
a. run nested procedure copy to copy integers into runs
1. use the following variable:
buf for the integer read from the input file
2. read the input file to obtain the integer
3. write the read integer into the specified file
to copy the run to
4. if end of file is encountered in the input file,
set eor equal to true
5. else, set eor equal to value equal to the result
of the comparison of buf > the next integer to
be read
b. repeat the procedure copyrun until eor is equal to
true
2. when the first run of copyrun is completed, run copyrun
using sortfile and temporary file number 2 if end of file
is not encountered in sortfile
3. repeat procedure distribute until end of file in
encountered in sortfile
E. reset the first and second temporary files for reading
F. rewrite the sortfile to wipe it clean in preparation for
merging the sorted runs back together
G. set variable l for tracking the number of records to 0
H. run procedure merge to merge the sorted runs back together.
1. while eof is not encountered in either of the temporary
run files do the following:
a. run nested procedure mergerun
1. if the next integer in the first temporary file is
less than the next integer in the second temporary
file then do the following:
a. run procedure copy as described in step
4.D.1.a above using the first temporary file
as the input file and sortfile as the output
file
b. if eor has been set to true, then run
procedure copyrun as described in step 4.D.1
using the second temporary file as the input
file and sortfile as the output file
2. else do the following:
a. run procedure copy as described in step
4.D.1.a above using the second temporary file
as the input file and sortfile as the output
file
b. if eor has been set to true, then run
procedure copyrun as described in step 4.D.1
using the first temporary file as the input
file and sortfile as the output file
3. continue procedure mergerun until eor is true
b. add 1 to l to track the number of runs
2. while eof is not encountered in the first temporary file,
do the following:
a. run procedure copyrun as described in step 4.D.1 using
the first temporary file as the input file and
sortfile as the output file
b. add 1 to l to track the number of runs
3. while eof is not encountered in the second temporary file,
do the following:
a. run procedure copyrun as described in step 4.D.1 using
the second temporary file as the input file and
sortfile as the output file
b. add 1 to l to track the number of runs
I. repeat procedure naturalmerge until variable l that tracks
the number of runs is equal to one which signals that sorting
has been completed.
5. The main of the program will be executed in the following manner:
A. reset sortfile to assign the file name contained in the
constant NUMSORT to it
B. rewrite tmp1 to assign the file name contained in the constant
TEMP1 to the first temporary file
C. rewrite tmp2 to assign the file name contained in the constant
TEMP2 to the second temporary file
D. run procedure naturalmerge to sort the file of integers
*)
(**************************************************************************)
(*
Constant dictionary:
NUMSORT='sortnums.dat' for the file to be sorted
TEMP1='temp1.dat' for the first temporary file
TEMP2='temp2.dat' for the second temporary file
*)
(**************************************************************************)
(*
Type dictionary:
nums=file of integer - binary file that contains the integers
*)
(**************************************************************************)
(*
Variable dictionary:
sortfile:nums - for file of integers to be sorted
tmp1:nums - for the first temporary file
tmp2:nums - for the second temporary file
*)
(**************************************************************************)
program mergsort (input,output);
const
NUMSORT='sortnums.dat'; {sorted output file}
TEMP1='temp1.dat'; {temporary file for sorting}
TEMP2='temp2.dat'; {temporary file for sorting}
type
nums=file of integer; {file type}
var
sortfile, {sorted data}
tmp1, {temporary sort file}
tmp2:nums; {temporary sort file}
(***************************************************************************)
(* Procedure to sort numbers file *)
procedure naturalmerge (var a,b:nums);
var
l:integer; {number of runs written to files during merge}
var
eor:boolean; {set to true when end of run is discovered}
(*****************************************************************)
(* Procedure to copy item from file x to y and set eor *)
procedure copy (var x,y:nums);
var
buf:integer; {randomly generated number}
begin {copy}
read (x,buf);
write (y,buf);
if eof(x) then
eor:=true
else
eor:=buf > x^;
end; {copy}
(*****************************************************************)
(* Procedure to copy one run from source file to temp file *)
procedure copyrun (var x,y:nums);
begin {copyrun}
repeat
copy (x,y);
until eor;
end; {copyrun}
(*****************************************************************)
(* Procedure to call copyrun to distribute records from the source
file in to runs contained in two temporary files *)
procedure distribute;
begin {distribute}
repeat
copyrun (sortfile,a);
if not eof(sortfile) then
copyrun (sortfile,b);
until eof(sortfile);
end; {distribute}
(*****************************************************************)
(* Procedure to merge runs in temporary files back into sortfile *)
procedure mergerun;
begin {mergerun}
repeat
if (a^ < b^) then
begin {if statement}
copy (a,sortfile);
if eor then
copyrun (b,sortfile);
end {if statement}
else
begin {else statement}
copy (b,sortfile);
if eor then
copyrun (a,sortfile);
end; {else statement}
until eor;
end; {mergerun}
(*****************************************************************)
(* procedure to call mergerun to merge files back together *)
procedure merge;
begin {merge}
while not eof(a) and not eof(b) do
begin {while statement}
mergerun;
l:=l + 1;
end; {while statement}
while not eof(a) do
begin {while statement}
copyrun (a,sortfile);
l:=l + 1;
end;
while not eof(b) do
begin {while statement}
copyrun (b,sortfile);
l:=l + 1;
end; {while statement}
end; {merge}
(*****************************************************************)
begin {naturalmerge}
repeat
rewrite (a);
rewrite (b);
reset (sortfile);
distribute;
reset (a);
reset (b);
rewrite (sortfile);
l:=0;
merge;
until l=1;
end; {naturalmerge}
(***************************************************************************)
begin {main}
reset (sortfile,numsort);
rewrite (tmp1,temp1);
rewrite (tmp2,temp2);
naturalmerge (tmp1,tmp2);
close (sortfile);
close (tmp1);
close (tmp2);
end. {main}