EXPLANATION FILE OF PROGRAM MERGE
               =================================


    Merge Sort
    ----------

    Suppose that we have two ordered arrays of integers, say a() and b(). If we
  want to merge them inti another ordered array, say c(), we can use a simple
  algorithm. First compare a(0) and b(0). Whichever is smaller, say b(0), put
  into c(0). Next compare a(0) and b(1). Whichever is smaller, say b(1), put
  into c(1). Next compare a (1) and b(2). Whichever is smaller, say a(0), put
  into c(3). Next compare a[1] and b [2] , and so on. Eventually one of the
  arrays a() or b() will be exhausted. At this point, the remainder of the ele-
  ments in the other array must be copied into c(). This is done by program
  Merge.
 
    The array c() is assumed to contain enough space to hold both a() and b().
  The programmer must make certain that the bounds on c() are not overrun. 

    In contrast to a bubble sort, a merge sort is very efficient. We will write
  a function called mergesort() to act on an array key[] , which has a size that
  is a power of 2. The "power of 2" requirement will help to make the explana-
  tion simpler. ln the exercises, we indicate how this restriction is removed.
  To understand how merge sort works, let us suppose that key[] contains the
  following 16 integers: 

               4 3 1 67 55 8 0 4 -5 37 7 4 2 9 1 -1 

    The algorithm will work on the data in a number of passes. The following ta-
  ble shows how we want the data to look after each pass: 
 
    unordered data:  4     3 	1 	67 	55 	8 	0       4
                    -5    37  	7 	 4 	2 	9 	1      -1 	   
    first pass:      3     4    1       67 	8 	55 	0 	4
     	            -5 	  37 	4 	7 	2 	9      -1       1 		   
    second pass:     1     3 	4 	67 	0 	4 	8      55
                    -5 	   4 	7 	37 	-1 	1 	2       9 		   
    third pass:      0 	   1 	3 	4 	4 	8 	55     67
                    -5 	  -1 	1 	2 	4 	7 	9      37	   
    fourth pass:    -5 	  -1 	0 	1 	1 	2 	3 	4
                     4 	   4 	7 	8 	9 	37 	55     67
                       		   
    After the first pass we want each successive pair of integers to be in
  order. After the second pass we want each successive quartet of integers to be
  in order. After the third pass we want each successive octet of integers to be
  in order. Finally, after the fourth pass we want all 16 of the integers to be
  in order. At each stage merge() is used to accomplish the desired ordering.
  For example, after the third pass, we have the two subarrays:

    0  1  3  4  4  8  55  67  and  -5  -1  1  2  4  7  9  37

  which are both in order. When we merge these two subarrays, we obtain the com-
  pletely ordered array given above. Surprisingly, the code that accomplishes
  this is quite short.

  From [BIBLI 09]
---------------------------------------
End of file merge.txt