How do you sort integers into a new file in ascending order from 2 input files?

Question

I'm trying to create a program which takes integer input from two files. I have two files with integers in ascending order, and the output file should merge those two into one file, kept in ascending order.

while((fscanf(inputFile1, "%d", &temp1) == 1) && (fscanf(inputFile2, "%d", &temp2) == 1))
{
  printf("temp1: %d\n", temp1);
  printf("temp2: %d\n", temp2);

  if (temp1 > temp2)
  {
     fprintf(outputFile, "%d\n", temp2);
     fprintf(outputFile, "%d\n", temp1);
  }
  else if (temp1 < temp2)
  {
     fprintf(outputFile, "%d\n", temp1);
     fprintf(outputFile, "%d\n", temp2);
  }
  else if (temp1 == temp2)
  {
     fprintf(outputFile, "%d\n", temp1);
     fprintf(outputFile, "%d\n", temp2);
  }
}

File 1    File 2
5         1
10        43
30        55
50        98
345       500

Output
1
5
10
43
30
55
50
98
345 
500

It's almost complete but there's an issue when one of the files has a number smaller/larger than a previous line in another file (like 30 > 43). How can I fix this issue, so that the output is completely sorted?

Answer 1

You're reading one number from each file, which will fail when you would have to take two consecutive numbers from the same file.

Instead, you should read numbers from file #1 and #2, and keep reading from the file which number is smaller until it's greater that the last number read from the other file.

Answer 2

Consider a practical case, where you had two columns of numbers in ascending order, and you wanted to read them out in ascending order. You would most likely keep one finger on each column, pointing to the next value in that column. You choose the smaller, read it aloud, and move that finger down. This is the algorithm your code should implement.

Let's look at the algorithm in pseudocode.

First, we need to read the first value from both files. It may happen that one of the source files is empty, in which case we need to just output the contents of the other file:

Read value1 from the first file.
If we cannot, then:
    Loop:
        Read value2 from the second file.
        If we cannot: Return.
        Output value2
    End loop
End if

Read value2 from the second file.
If we cannot, then:
    Loop:
        Output value1
        Read value1 from the first file.
        If we cannot: Return.
    End loop
End if

That takes care of the initial condition, and now we have value1 from the first file, and value2 from the second file, and can enter into our main loop.

On each iteration, we output the smaller value, and read the next number from that source file -- just as if we moved our finger down in the column we read aloud.

Again, if we run out of data, we output the contents of the other file.

Note that I've chosen a logic where all equal values are output from the first file first (i.e., if both columns have an equal value, we read (all the equal values in) the first column first, and from the second column afterwards). This should make this a stable sort.

Loop:

    If value1 <= value2, then:
        Output value1
        Read value1 from the first file.
        If we cannot, then:
            Loop:
                Output value2
                Read value2 from the second file.
                If we cannot: Return.
            End loop
        End if
    Else:
        Output value2
        Read value2 from the second file.
        If we cannot, then:
            Loop:
                Output value1
                Read value1 from the second file.
                If we cannot: Return.
            End loop
        End if
    End if
End loop

In C, this should be very straightforward to implement as a function; perhaps void interleave_ints(FILE *in1, FILE *in2, FILE *out).

Note that all the loops above are infinite (i.e., while (1) { ... } or do { ... } while(1); or for (;;) { ... }), and in the function, you can use return; to return back to the caller.