//  Merge sort algorithm for n elements 
//  in a Monitored array, a.


#include <iostream.h>
#include "array.h"

void swap (int, int);
extern MArray a;

void simpleMerge (int, int, int);
void merge (int, int);

void merge (int n)
{  merge (0, n-1); 
}

void merge (int start, int finish)
{  int size = finish - start + 1;

   if (size<=1) return;
   int middle = start + size/2 - 1;
   //  merge (start, middle);
   merge (middle+1, finish);
   merge (start, middle);
   simpleMerge (start, middle+1, finish);
}

void simpleMerge (int first, int second, int third)
{  int i = first;
   int j = second;
   int l = -1;
   int n = a.getSize();
   int left, right;		// controlling order of operand eval

   while (i<second && j<=third)
   { left = a[i];		// control order of operand eval
     right = a[j];
     //  left = a[i];
     if (left <= right)		// if (a[i] <= a[j]) 
	{  l++;
	   a[l+n] = a[i];
	   i++;
	}
     else 
	{  l++;
	   a[l+n] = a[j];
	   j++;
	}
   }
   if (i>=second)
	while (j<=third)
	  {  l++;
	     a[l+n] = a[j];
	     j++;
	  }
   else while (i<second)
	  {  l++;
	     a[l+n] = a[i];
	     i++;
	   }
   for (i=0; i<=third-first; i++)
	a[first+i] = a[i+n];
}