5. Merging Files

Quite often data held in two separate files need to be merged (combined) to form a single file.

Consider you have two similar files containing this data

File A : 1,5,7,9

File B : 2, 3, 8, 6, 25, 53

The simplest way of merging them is to copy file A into a new file called 'C', then append the data from file B to it. The resulting file looks like this

File C: 1, 5, 7, 9, 2, 3, 8, 6, 25, 53

This is fine if all you wanted to do was to store data in one place. But what if it is important that the data is sorted before being stored?

In this case the merge algorithm needs to check the relationship between the data in each file before inserting them into the new file.

Let's say that the merge file has to be in ascending order.

An algorithm to do this is show below

    Read first data item from File A 
    Read first data item from File B
       While File A has data remaining  AND File B has data remaining
         If (item A < item B)
            Store item A into File C
            Read next item from File A  
         End if
          Else 
            Store item B into File C
            Read next item from File B      
          End if  
       Repeat
       Copy remaining data into File C
  

The algorithm starts with the first item from each file and compares them. The lowest value is stored and the other one is retained for the next comparison. The loop keeps on going until one of the files is empty. Then the remaining data is added to File C

It can be hard to follow an algorithm, especially with loops involved. So one way is to see the result as it steps through each loop.

Consider the two files mentioned above

File A : 1,5,7,9

File B : 2, 3, 8, 25, 33

Let's follow what is happening at each step

The result is a merged, sorted file. This algorithm is a bit too simple because what happens if both A and B have equal values? What could be done to merge them in descending order? These points are left for you to consider how you would modify the merge algorithm.