D. Improving the basic merge sort: two possible improvements suggest 
      themselves immediately, and entail minimal extra work.

      1. If we had four scratch files instead of three, we could combine the
         merging and redistribution into one operation as follows:  On each
         pass, we use two files for input and two for output.  We write the 
         runs generated alternately to the two output files.  After the pass,
         we switch the roles of the input and output files.

         a. Example: original file:     B D E C F A G H

                  initial distribution: B E F G         (File SCRATCH1)
                                        D C A H         (File SCRATCH2)

                  (remember we ignore runs existing in the raw data)

                  after first pass:     BD AF           (File SCRATCH3)
                                        CE GH           (File SCRATCH4)

                  after second pass:    BCDE            (File SCRATCH1)
                                        AFGH            (File SCRATCH2)

                  after third pass:     ABCDEFGH        (File SCRATCH3)

         b. Code: TRANSPARENCY

         c. Analysis:

            i. Space: four files, two of which must now be of length n,
               since we don't know ahead of time, in general, whether we will 
               have an odd or even number of passes.  (The sorted file will
               end up on either the first or third scratch file.)  The
               other two files can be of length n/2.  As before, we can use
               the output file as one of the scratch files, so the extra
               space needed is one file of length n plus two of length n/2

               = total scratch space for 2n records

               Plus internal memory for 4 file buffers.

           ii. Time: Because we have an initial distribution pass before
               we start merging, we have a total of

                n (1 + ceil(log n)) reads =  2n(1 + ceil(log n)) transfers
 
          iii. We have gained almost a factor of 2 in speed, at the cost
               of doubling the scratch file space.

          d. This algorithm is known as BALANCED 2-WAY MERGE SORT.