Sorting algorithms

External merge

Sorting data that is not stored in the main memory of the computer is called external sorting. Typically, in this case data is stored in a file with sequential access. The idea of Mergesort can be used to solve the external sorting problem.

The following procedure merge_files merges two sorted files into one new sorted file (Figure 1).

Bild 1: Merging two sorted files into one

The code is written in Visual Basic.

' merges two sorted files file1 and file2;
' creates or overwrites file3 as sorted file
Sub merge_files(file1, file2, file3) 
    Open file1 For Input As #1
    Open file2 For Input As #2
    Open file3 For Output As #3

    If EOF(1) Or EOF(2) Then    ' one file is empty
        If EOF(1) Then  ' file1 is empty
            copy 2, 3
        Else            ' file2 is empty
            copy 1, 3
        End If
    Else                ' both files are not empty
        Input #1, x
        Input #2, y
        Do
            ' compare x and y
            If x < y Then
                ' element x is smaller; write x to file3
                ' and read new x provided there is any;
                ' otherwise copy the rest of file2 to file3
                Print #3, x
                If Not EOF(1) Then
                    Input #1, x
                Else
                    Print #3, y
                    copy 2, 3
                    Exit Do
                End If
            Else
                ' element y is smaller; write y to file3
                ' and read new y provided there is any;
                ' otherwise copy the rest of file1 to file3
                Print #3, y
                If Not EOF(2) Then
                    Input #2, y
                Else
                    Print #3, x
                    copy 1, 3
                    Exit Do
                End If
            End If
        Loop
    End If

    Close #1
    Close #2
    Close #3
End Sub


Sub copy(i, j)    ' copy (rest of) #i to #j
    Do While Not EOF(i)
        Input #i, y
        Print #j, y
    Loop
End Sub

The following program is used for the purpose of testing. Procedure write_files creates two sorted files and procedure output_file shows the result.

Private Sub Command1_Click()    ' test program
    write_files "file1.txt", "file2.txt"
    merge_files "file1.txt", "file2.txt", "file3.txt"
    output_file "file3.txt"
End Sub

Sub write_files(file1, file2) ' for testing
    ' write sorted file1
    Open file1 For Output As #1
    Print #1, 10
    Print #1, 14
    Print #1, 18
    Print #1, 22
    Close #1

    ' write sorted file2
    Open file2 For Output As #2
    Print #2, 11
    Print #2, 13
    Print #2, 15
    Print #2, 17
    Print #2, 29
    Print #2, 31
    Close #2
End Sub

Sub output_file(file3)  ' show result file3
    Open file3 For Input As #3
    Do While Not EOF(3)
        Input #3, x
        Debug.Print x
    Loop
    Close #3
End Sub