In this assignment, we are using recursion to sort a table of integers.

What are we doing?

We will have subroutines called MergeSort and Merge.

MergeSort will do the following:

     1. Start with an array A of size N.

     2.  If N is larger than 1, continue.  Otherwise stop.

     3. Calculate H = N / 2.

     4. Create a temporary array B of size N.

     5. Split A into two smaller arrays A(1 : H) and A(H + 1 : N).

     6. Create two temporary arrays F and G of sizes H and N - H.

     7. Set F = A(1 : H) and G = A(H + 1 : N),

     8. Call Mergesort on array F (providing its size) and again on
        array G (providing its size).

     9. Call Merge (as described below), passing it the three tables
        F, G and B and their sizes.

    10. Set A = B.

The arguments for Merge are a table and the size of the table.

The Merge subroutine puts together two small sorted tables into one large sorted table. It works like this:

      1. We have three tables: table 1, table 2 and the merged table.

      2. Do while NOT the end of either table 1 or table 2

      3.   If table 1's value < table 2's value

      4.     Copy table 1's entry into the merged table

      5.     Increment table 1's index

      6.   Else (table 1's value > table 2's value)

      7.     Copy table 2's entry into the merged table

      8.     Increment table 2's index

      9.   End If

     10.   Increment the merged table index

     11. End Do

     12. Do while NOT the end of table 1
 
     13.   Copy table 1's entry into the merged table

     14.   Increment table 1's index

     15.   Increment the merged table index

     16. End Do

     17. Do while NOT the end of table 2
 
     18.   Copy table 2's entry into the merged table

     19.   Increment table 2's index

     20.   Increment the merged table index

     21. End Do

The arguments for Merge are the three tables and their sizes.

We will have an input file called "dataG1.txt" containing 20 integers and a second input file called "dataG2.txt" containing 200 integers.

Read each file with input redirection and put the integers into appropriate-sized arrays. Print out each array. (I suggest 10 numbers per line.)

Call the Merge subroutine on each of these arrays.

Print each array again after sorting.

Notes

The subroutine called MergeSort is a recursive subroutine. You will need the keyword "Recursive" in the heading:

     Recursive Subroutine MergeSort(Table, N)

MergeSort is otherwise much like any other subroutine.

Notice the special case here in which one of the tables has only 1 element. If Merge finds a table of 1 element, there is little to do.

Feel free to try this with larger or smaller arrays or to try it by hand.

It might be interesting in Merge to print out the two input arrays each time (at least when we have only 20 numbers) so we can watch what is happening, and then in MergeSort to print out the merged table (a part of the large overall array).

Notice we are using assignment statements for whole arrays, as in A = B. The ability to do whole array operations is a nice feature of FORTRAN.

Your program should be well structured and properly documented. You may want to use more subroutines as well. Do not use any GO TOs. Do use IMPLICIT NONE.

You need to compile and link your program as usual.