Question 7 of 8: File I/O — Merging Two Sorted Files

Question 7: 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.

Strategy. This is the classic external two-way merge building block: keep one buffered record from each input file "in hand" at all times, repeatedly write out whichever of the two is not lexicographically greater (breaking left/right ties by writing the left one first, which keeps the merge stable), and refill only the file that record came from. When one file runs out of records, the remaining records of the other file are already sorted relative to everything written so far, so they can simply be copied through unchanged. This never needs to hold more than two records in memory regardless of how large the files are.

Given. Two pre-sorted input files, and one output file name, each record up to 80 characters (including the terminating newline) and possibly containing embedded spaces; the two files may have different record counts.

Find. A program that produces one output file containing every record from both inputs, in sorted order.

1. Buffer exactly one record per input file. A record may contain spaces, so it must be read with fgets (which reads until the newline or the buffer limit), never with scanf("%s") (which stops at whitespace and would silently truncate a multi-word record).
2. Write the program.

   #include <stdio.h>
   #include <string.h>
   
   #define REC_LEN 81   /* 80 chars + terminating NUL after fgets strips nothing */
   
   int main(void)
   {
       char nameIn1[100], nameIn2[100], nameOut[100];
       char rec1[REC_LEN], rec2[REC_LEN];
       FILE *f1, *f2, *fout;
       int have1, have2;
   
       printf("Enter names of the two input files and the output file: ");
       scanf("%99s %99s %99s", nameIn1, nameIn2, nameOut);
   
       f1 = fopen(nameIn1, "r");
       f2 = fopen(nameIn2, "r");
       fout = fopen(nameOut, "w");
       if (!f1 || !f2 || !fout) {
           printf("Could not open all required files.\n");
           return 1;
       }
   
       have1 = (fgets(rec1, REC_LEN, f1) != NULL);
       have2 = (fgets(rec2, REC_LEN, f2) != NULL);
   
       /* Merge while both files still have a buffered record. */
       while (have1 && have2) {
           if (strcmp(rec1, rec2) <= 0) {       /* rec1 <= rec2: write rec1 (stable on ties) */
               fputs(rec1, fout);
               have1 = (fgets(rec1, REC_LEN, f1) != NULL);
           } else {
               fputs(rec2, fout);
               have2 = (fgets(rec2, REC_LEN, f2) != NULL);
           }
       }
   
       /* Drain whichever file still has records left -- already sorted, so
          just copy the rest through record by record. */
       while (have1) {
           fputs(rec1, fout);
           have1 = (fgets(rec1, REC_LEN, f1) != NULL);
       }
       while (have2) {
           fputs(rec2, fout);
           have2 = (fgets(rec2, REC_LEN, f2) != NULL);
       }
   
       fclose(f1); fclose(f2); fclose(fout);
       return 0;
   }

   Comparing with strcmp directly on the fgets buffers (newline included) is safe: the newline sorts as a normal character and never changes the relative order of two distinct records, since it only ever appears at the very end of each buffer.
3. Confirm on a small worked example. Merging {apple, cherry, fig, kiwi} with {banana, date, fig, grape, lime} interleaves by comparison at every step, and the trailing drain loop is what correctly appends grape and lime once the first file is exhausted. $$\boxed{\text{merged} = \text{apple, banana, cherry, date, fig, fig, grape, kiwi, lime}}$$