// yasuhara, 10 Aug 2000


void mergesort(int A[], int N) 
{
  mergesort_help(A, 0, N-1);
}


// runs in O(n log n), where n == hi - lo

void mergesort_help(int A[], int lo, int hi) 
{
  if (hi - lo >= 1) {  // check for base case
    // recursively sort each half
    int mid = (lo + hi) / 2;
    mergesort_help(A, lo, mid);
    mergesort_help(A, mid + 1, hi);

    // merge sorted half-arrays into one
    merge(A, lo, mid, hi);
  }
}


// precondition: subarrays A[lo..mid] and A[mid+1..hi] are sorted (but
// A[lo..hi] is not necessarily sorted)
//
// postcondition: A[lo..hi] is result of interleaving elements of the
// subarrays such that A[lo..hi] is sorted
//
// runs in O(n) time, where n == hi - lo

void merge(int A[], int lo, int mid, int hi)
{
  // fir and sec will step through indices of subarrays A[lo..mid] and
  // A[mid+1..hi], respectively
  int fir = lo;  int sec = mid + 1;

  // tempArray will store sorted version of A[lo..hi]; 
  // i steps through indices of this array 
  int tempArray[MAX_SIZE];
  for (int i = 0; i <= hi - lo; ++i) {  
    // sec > hi iff all elements of A[mid+1..hi] have been added to
    // tempArray; fir <= mid iff elements of A[lo..mid] remain to be
    // added to tempArray
    if (sec > hi ||  
	(fir <= mid && A[fir] < A[sec])) {
      // store A[fir] in tempArray[i], *then* increment fir
      tempArray[i] = A[fir++];  
    } else {
      // store A[sec] in tempArray[i], *then* increment sec
      tempArray[i] = A[sec++];
    }
  }

  // copy result from tempArray into original array
  for (int n = 0; n <= hi - lo; ++n) {
    A[lo + n] = tempArray[n];
  }
}