# 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 ```

 H.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 26.11.2006   Updated: 04.06.2018