Algorithm for Merging Sequential Files

The algorithm is relatively simple:

Open the old master file for reading and a new master file for writing
Read the records from the old master file and write them to the new master file until the new record insertion point is found
Write the new record into the new master file
Write the remaining records into the new master file

In pseudo-code:

begin
open old master file for reading
open new master file for writing
read new_record (from keyboard?)
variable: inserted = false
while not eof (old master file) do
 begin
  read (old master file, record)
  if not inserted do
   if new_record.key <= old master file.key then
    begin
     write (new master file, new_record)
     inserted = true
    end
   write ((new master_file record, old master file record)
 end
end

Sample data:

Old Master File:

adams
black
carter
dobson
ellison
smith

New record: coles

read master file: adams: coles > adams so read copy adams to new master file and read next from old master file
read master file: black: coles > black so copy black to new master file and read next from old master file
read master file: carter: carter> black so copy carter to new master file and read next from old master file
read master file: dobson: coles <= dobson so copy coles to new master file, copy dobson to new master file and read next from old master file
read ellison from old master file and write to new master file (inserted now true so skips second if)
read smith from old master file and write to new master file (inserted now true so skips second if)

Back