Question 5 of 9: File I/O — Merging Two Sorted Files

Question 5: File I/O — Merging Two Sorted Files (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Two input files, each already sorted, whose records are newline-terminated strings of at most 80 characters (including the newline); record counts may differ between the two files; a third, output file name is also supplied by the user.

Find. A program that merges the two sorted input files into a single sorted output file.

Approach and strategy. This is the classic external 2-way merge step from merge sort. Keep one line-buffer per input file and a "currently loaded" flag for each; read one line ahead from each file at start-up. At each step, compare the two currently-held lines lexicographically (strcmp), write the smaller (or either, if equal) to the output file, and refill only the buffer that was just written from its source file. When one file is exhausted, stop comparing and simply copy the remainder of the other file's lines straight through — this handles unequal record counts with no special-casing beyond a flag per file.

1. State the strategy (as required) and confirm it needs only $O(1)$ extra buffering. Because each file is already sorted, the smaller of the two "next" records is always the correct next record for the merged output — the same invariant used by the merge step of merge sort — so the whole file never needs to be loaded into memory, only one 80-character line per input file at a time.
2. Write the program.

   #include <stdio.h>
   #include <string.h>
   
   #define MAXREC 80
   
   int main(void)
   {
       char name_a[256], name_b[256], name_out[256];
       char line_a[MAXREC], line_b[MAXREC];
       FILE *fa, *fb, *fout;
       int have_a, have_b;
   
       printf("Enter first sorted input file: ");
       scanf("%255s", name_a);
       printf("Enter second sorted input file: ");
       scanf("%255s", name_b);
       printf("Enter output file name: ");
       scanf("%255s", name_out);
   
       fa = fopen(name_a, "r");
       fb = fopen(name_b, "r");
       fout = fopen(name_out, "w");
   
       /* prime one line from each file */
       have_a = (fgets(line_a, MAXREC, fa) != NULL);
       have_b = (fgets(line_b, MAXREC, fb) != NULL);
   
       while (have_a && have_b) {
           if (strcmp(line_a, line_b) <= 0) {
               fputs(line_a, fout);                 /* A's record is <= B's */
               have_a = (fgets(line_a, MAXREC, fa) != NULL);
           } else {
               fputs(line_b, fout);                 /* B's record is smaller */
               have_b = (fgets(line_b, MAXREC, fb) != NULL);
           }
       }
       /* copy through whichever file still has records left */
       while (have_a) {
           fputs(line_a, fout);
           have_a = (fgets(line_a, MAXREC, fa) != NULL);
       }
       while (have_b) {
           fputs(line_b, fout);
           have_b = (fgets(line_b, MAXREC, fb) != NULL);
       }
   
       fclose(fa); fclose(fb); fclose(fout);
       return 0;
   }
   

3. Confirm on a small worked example. File A = {"apple","mango","zebra"} (3 records), file B = {"banana","kiwi"} (2 records, unequal count). Tracing the merge: compare apple/banana → apple; compare mango/banana → banana; compare mango/kiwi → kiwi; B exhausted, copy remaining A records mango, zebra straight through. Output: apple, banana, kiwi, mango, zebra — sorted, and all 5 records are present exactly once. $$\boxed{\text{merged output}=\{\text{apple, banana, kiwi, mango, zebra}\}}$$