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.

Strategy. This is the merge step of merge sort applied to two files instead of two in-memory arrays: since both inputs are already individually sorted, the smallest not-yet-written record overall is always one of the two records currently "at the front" of the two files, so the program never needs to hold more than one record from each file in memory at a time. It reads one record from each file, repeatedly writes whichever of the two current records is lexicographically smaller and refills only that side, and once one file is exhausted it copies the remainder of the other file straight through (their relative order is already correct, and every one of those remaining records is $\ge$ everything already written, since the exhausted file's last record was still $\le$ the still-open file's current record at the moment it ran out).

Given. Two files, each pre-sorted line by line (records up to 80 characters including the newline); a third output filename.

Find. One output file containing all records from both inputs in sorted order.

1. Write the merge.

   #include <stdio.h>
   #include <string.h>
   
   #define MAXREC 81   /* 80 chars including '\n', plus '\0' */
   
   int main(void)
   {
       char nameA[256], nameB[256], nameOut[256];
       char recA[MAXREC], recB[MAXREC];
       FILE *fa, *fb, *fout;
       int haveA, haveB;
   
       printf("Enter first sorted file: ");  scanf("%255s", nameA);
       printf("Enter second sorted file: "); scanf("%255s", nameB);
       printf("Enter output file: ");        scanf("%255s", nameOut);
   
       fa = fopen(nameA, "r");
       fb = fopen(nameB, "r");
       fout = fopen(nameOut, "w");
       if (!fa || !fb || !fout) { printf("Could not open a file.\n"); return 1; }
   
       haveA = (fgets(recA, MAXREC, fa) != NULL);   /* "front" record of file A */
       haveB = (fgets(recB, MAXREC, fb) != NULL);   /* "front" record of file B */
   
       while (haveA && haveB) {
           if (strcmp(recA, recB) <= 0) {
               fputs(recA, fout);
               haveA = (fgets(recA, MAXREC, fa) != NULL);
           } else {
               fputs(recB, fout);
               haveB = (fgets(recB, MAXREC, fb) != NULL);
           }
       }
       /* copy whatever remains of whichever file is not yet exhausted */
       while (haveA) { fputs(recA, fout); haveA = (fgets(recA, MAXREC, fa) != NULL); }
       while (haveB) { fputs(recB, fout); haveB = (fgets(recB, MAXREC, fb) != NULL); }
   
       fclose(fa); fclose(fb); fclose(fout);
       return 0;
   }

2. Trace it on two small sorted files. File A = {apple, cherry, mango, zebra}, File B = {banana, date, fig, kiwi, yam} (5 records – deliberately a different count from A, since the files may differ in length). Merging compares the two front records repeatedly: apple < banana (take A), banana < cherry (take B), cherry < date (take A), date < mango (take B), fig < mango (take B), kiwi < mango (take B), mango < yam (take A), yam < zebra (take B) — at which point B is exhausted, and the second drain loop copies A's one remaining record, zebra, straight through. Nine comparisons-and-writes for $4+5=9$ records, matching the $m+n$ output-step count: $$\boxed{\text{output} = \text{apple, banana, cherry, date, fig, kiwi, mango, yam, zebra}}$$