External sort compo?

[yetifoot]

OK. I have written an explanation, i hope it's useful! It explains the process I used to merge two files into one, first in a verbose psuedocode, then with some generic BASIC code. This omits any buffering code and just attempts to explain the actual merging.

Code:

This file outlines a subroutine that merges two input files of sorted data to an output file.

Definitions:

InFile1, InFile2 - The input files, these will be two files that contain sorted records.  They
                   do not have to contain an equal number of records.
OutFile          - The output file.  This will be the result of merging the two input files.
nrl1, nrl2       - The number of records still to process in each input file.
temp1, temp2     - These contain the last read record from each input file.

Pseudocode:

[1]  Open InFile1 and InFile2 for reading, open OutFile for writing
[2]  Calculate nrl1, and nrl2 by obtaining the LOF (size of file) of each input, and dividing by the record size.
[3]  Read a record from each input into appropriate temp variable.

[4]  While (nrl1 <> 0) AND (nrl2 <> 0) (ie: there is still data to read in both files)
[5]    Compare temp1 to temp2
[6]    If temp1 < temp2 Then           (if the record from InFile1 compares as less than than the record from InFile2)
[7]      Put temp1 to OutFile
[8]      Decrement nrl1                (we have now put the record with the lowest value (temp1 from InFile1) to the output,
                                        and decremented the counter for InFile1)
[9]      If nrl1 <> 0 Then Read from InFile1 to temp1 (because we have put the record from InFile1 we now need to refill
                                                       temp1)
[10]   Else                            (record from InFile1 compares as greater than or equal to the record from InFile2)
                                       (Note: in the case of equality it doesn't really matter which is put to file first)
[11]     Put temp2 to OutFile
[12]     Decrement nrl2                (we have now put the record with the lowest value (temp2 from InFile2) to the output,
                                        and decremented the counter for InFile2)
[13]     If nrl2 <> 0 Then Read from InFile2 to temp2 (because we have put the record from InFile2 we now need to refill
                                                       temp2)
[14]   End If
[15] Wend

[16] At this point one of the input files has been exhausted.  Therefore we can safely put all the remaining records
     in the non-exausted file to the output.  (because both inputs are already sorted).  Only one of the following loops
                                               will actually be run.  We should also remember to flush temp1, or temp2
                                               depending on which still has leftover data)

[17]  While nrl1 > 0
[18]    Read a record from InFile1 and put it to OutFile
[19]    Decrement nrl1
[20]  Wend

[21]  While nrl2 > 0
[22]    Read a record from InFile2 and put it to OutFile
[23]    Decrement nrl2
[24]  Wend

[25]  Close all 3 files.

BASIC Code:

' Note integer type is assumed 4 bytes.
Sub MergeFiles(InFile1 As String, InFile2 As String, OutFile As String)
Dim nrl1 As Integer
Dim nrl2 As Integer
Dim temp1 As Integer
Dim temp2 As Integer
Dim record_size As Integer
  
  record_size = 4 ' Size of Integer
  Open InFile1 For Binary As #1
  Open InFile2 For Binary As #2
  Open OutFile For Binary As #3

    nrl1 = LOF(1) \ record_size
    nrl2 = LOF(2) \ record_size
    
    If (nrl1 = 0) OR (nrl2 = 0) Then Exit Sub ' Just to show that zero record files should not be passed to this sub.
                                              ' As they will cause failure.  This could be coded for, but we don't do
                                              ' that here.

    Get #1, , temp1
    Get #2, , temp2

    ' The main loop

    While (nrl1 <> 0) AND (nrl2 <> 0)
      If temp1 < temp2 Then
        Put #3, , temp1
        nrl1 = nrl1 - 1
        If nrl1 <> 0 Then Get #1, , temp1
      Else
        Put #3, , temp2
        nrl2 = nrl2 - 1
        If nrl2 <> 0 Then Get #2, , temp2
      End If
    Wend
    
    ' Only one of these actually runs.

    While nrl1 > 0
      Put #3, , temp1 ' This line appears first because there will be data left from the main loop
      nrl1 = nrl1 - 1
      If nrl1 <> 0 Then Get #1, , temp1
    Wend

    While nrl2 > 0
      Put #3, , temp2 ' This line appears first because there will be data left from the main loop
      nrl2 = nrl2 - 1
      If nrl2 <> 0 Then Get #2, , temp2
    Wend

  Close ' All
End Sub