// Chapter 9, pp 415 - 417

#include  // included for rand in main

#include 

const int MAX_SIZE = 12;

typedef int dataType;
typedef dataType arrayType[MAX_SIZE];

void Merge(dataType A[], int F, int Mid, int L)
// ---------------------------------------------------------
// Merges two sorted array segments A[F..Mid] and 
// A[Mid+1..L] into one sorted array.
// Precondition: F <= Mid <= L. The subarrays A[F..Mid] and
// A[Mid+1..L] are each sorted in increasing order.
// Postcondition: A[F..L] is sorted.
// Implementation note: This function merges the two
// subarrays into a temporary array, and copies the result
// into the original array A.
// ---------------------------------------------------------
{
   dataType TempArray[MAX_SIZE];    // temporary array

   // initialize the local indexes to indicate the subarrays
   int First1 = F;        // beginning of first subarray
   int Last1  = Mid;      // end of first subarray
   int First2 = Mid + 1;  // beginning of second subarray
	int Last2  = L;        // end of second subarray

	// while both subarrays are not empty, copy the
   // smaller item into the temporary array
	int Index = First1;    // next available location in
								  // TempArray
	for (; (First1 <= Last1) && (First2 <= Last2); ++Index)
   {  // Invariant: TempArray[First1..Index-1] is in order
      if (A[First1] < A[First2])
      {  TempArray[Index] = A[First1];
         ++First1;
      }
      else
      {  TempArray[Index] = A[First2];
         ++First2;
      }  // end if
   }  // end for

   // finish off the nonempty subarray

   // finish off the first subarray, if necessary
   for (; First1 <= Last1; ++First1, ++Index)
      // Invariant: TempArray[First1..Index-1] is in order
      TempArray[Index] = A[First1];

   // finish off the second subarray, if necessary
	for (; First2 <= Last2; ++First2, ++Index)
      // Invariant: TempArray[First1..Index-1] is in order
      TempArray[Index] = A[First2];

   // copy the result back into the original array
   for (Index = F; Index <= L; ++Index)
      A[Index] = TempArray[Index];
}  // end Merge

void Mergesort(dataType A[], int F, int L)
// ---------------------------------------------------------
// Sorts the items in an array into ascending order. 
// Precondition: A[F..L] is an array.
// Postcondition: A[F..L] is sorted in ascending order.
// Calls: Merge.
// ---------------------------------------------------------
{
   if (F < L)
   {  // sort each half
      int Mid = (F + L)/2;     // index of midpoint
      Mergesort(A, F, Mid);    // sort left half A[F..Mid]
      Mergesort(A, Mid+1, L);  // sort right half A[Mid+1..L]

      // merge the two halves
      Merge(A, F, Mid, L);
   }  // end if
}  // end Mergesort

// ******SAMPLE MAIN PROGRAM******
main()
{  arrayType A;
   int N, Size;

   // create an array of random integers
   Size = MAX_SIZE; // size of array
   for (N = 0; N < Size; ++N)
      A[N] = rand();

   cout << "The array before sorting is:\n ";
   for (N = 0; N < Size; ++N)
      cout << A[N] << " ";
   cout << "\n";

   // sort the array
   Mergesort(A, 0, Size-1);

   cout << "The array after sorting is:\n ";
   for (N = 0; N < Size; ++N)
      cout << A[N] << " ";
   cout << "\n";
   return 0;
}  // end main

    Source: geocities.com/siliconvalley/program/2864/ds/CHAP9

               ( geocities.com/siliconvalley/program/2864/ds)                   ( geocities.com/siliconvalley/program/2864)                   ( geocities.com/siliconvalley/program)                   ( geocities.com/siliconvalley)