//  Test a sort algorithm for data locality
//  by counting memory faults for various page sizes.
//  Use Monitored Array class (MArray) to tabulate faults.

int p;
#include <iostream.h>
#include <fstream.h>
#include "array.h"

void bubble(int);
void merge(int,int);
int min (int, int);
extern const int MAX= 10000;
extern MArray a(MAX);
ofstream out ("merge.out", ios::out);

void main ()
{ 
 
     for (int n=16; n<5000; n *= 2)
 //    for (int n=10; n<20; n *=3)
     {  a.setSize (n);
        for (p=4; p<n; p *= 2)		// page size = 8,16,32,...
          {  for (int i=0; i<n/2; i++) a[i] = n-2*i;	// worst case
	     for (i=n/2; i<n; i++) a[i] = 2*(n-i)-1;
             a.setFault(0);			// reset mem fault counter
   	     merge (0, n-1); 				// call sort algorithm
	     cout << "merge sort, n = " << n << " page size = " << p 
	          << ",  faults = " << a.getFault() << endl;
	     out << n << " "
		 << p << " "
		 << a.getFault() << endl;
	  }
     }
} 

int min (int x, int y)
{  if (x<=y) return x;
      else return y;
}