#include <iostream>

using namespace std;

const size_t DATA_SIZE = 100;
const int MAX_SIZE = 1000;
const int TRIALS = 1000;

const bool DEBUG = false;

void FillArray(int data[], size_t size);
void PrintArray(const int data[], size_t size);
void MergeSort(int data[], size_t start, size_t end);
void CopyArray(const int src[],  int dest[], size_t size);
bool BSearch(const int data[], size_t start, size_t end, int key);
void CheckArray(const int data[], const int copy[] , size_t size);
void CheckOrder(const int data[], size_t size);
void MissCheck(const int data[], size_t size);

int main() {

     int data[DATA_SIZE];
     int copy[DATA_SIZE];
   
     int trial;
     size_t size;

     for(size = 2; size <= DATA_SIZE; size++) {
         cout << "Testing Size " << size << ": ";
         for(trial = 1; trial <= TRIALS; trial ++) {
             if (DEBUG) {
                cout << "Trial " << trial << endl;
             } else {
                if (trial%100==0 ) {
                   cout << trial << "  "; 
                }
                if (trial == TRIALS) {
                   cout << endl;
                }
             }

             FillArray(data, size);
             CopyArray(data,copy, size);

             if (DEBUG) {
                 cout << "The initial array " << endl;
                 PrintArray(data, size);
                 cout << endl;
             }

             MergeSort(data, 0, size);

             if (DEBUG) {
                  cout << "The sorted array " << endl;
                  PrintArray(data, size);
                  cout << endl << endl;
             }
 
             CheckArray(data, copy, size);
             CheckOrder(data, size);
             MissCheck(data, size);
         }
     }

     return 0;
}

void FillArray(int data[], size_t size){
    size_t i;

    for(i=0;i<size; i++) {
        data[i] = rand() % MAX_SIZE;
    }
    return;
}

void PrintArray(const int data[], size_t size){
    size_t i;

    cout << data[0];
    for(i=1;i<size;i++) {
       cout << " " << data[i];
    }
    return;
}

void Merge(int data[], size_t start, size_t mid, size_t end) {
     // this should only be the size required, static or somehow not allocated
     // each time.
     int dest[MAX_SIZE];

     size_t i, posa, posb;

     i = 0;
     posa = start;
     posb = mid;

     // merge the two lists 
     while (posa < mid and posb < end) {
        if (data[posa] < data[posb]) {
           dest[i] = data[posa];
           posa++;
        } else {
           dest[i] = data[posb];
           posb++;
        }
        i++;
     }

     // finish the merge
     // one of these will not be executed
     while (posa < mid) {
        dest[i] = data[posa];
        posa++;
        i++;
     }

     while (posb < end) {
        dest[i] = data[posb];
        posb++;
        i++;
     }

     i = 0;
     for(posa = start; posa < end; posa++) {
        data[posa] = dest[i];
        i++;
     }
     return;
}

void MergeSort(int data[], size_t start, size_t end){
    size_t mid;

    if (start+1 < end) {
       mid = (start+end)/2;
       MergeSort(data, start, mid);
       MergeSort(data, mid, end);
       Merge( data, start, mid, end);
    }
    return;
}

void CopyArray(const int src[],  int dest[], size_t size){
    size_t i;

    for(i=0;i<size;i++) {
       dest[i] = src[i];
    }

    return;
}
bool BSearch(const int data[], size_t start, size_t end, int key){
    size_t mid;

    if (start > end) { 
       return false;
    }  

    mid = (start+end)/2;
    if (data[mid] == key) {
       return true;
    } else if (data[mid] > key and mid != start) {
       return BSearch(data, start, mid-1, key);
    } else {
       return BSearch(data, mid+1, end, key);
    }
    return false;
}

void CheckArray(const int data[], const int copy[] , size_t size){
     size_t i;

     if (DEBUG) {
         cout << "Checking for missing elements " << endl;
     }

     for(i=0;i<size; i++) {
        if (not BSearch(data, 0, size-1, copy[i] )  ) {
           cout << "\tError: "<< copy[i] 
                << " should be in the sorted list but is not" << endl;
        }
     }
     return;
}

void CheckOrder(const int data[], size_t size){
    size_t i;

    if (DEBUG) {
        cout << "Checking for data out of order " << endl;
    }

    for(i=1;i<size;i++) {
       if (data[i-1] > data[i]) {
          cout << "\tError: " <<  data[i-1] << " and " << data[i]
               << " are out of order " << endl;
       }
    }
    return;
}

void MissCheck(const int data[], size_t size){
     if (BSearch(data, 0, size-1, -1) ) {
         cout << "\tError: found -1 in the array" << endl;
     }
     if (BSearch(data, MAX_SIZE+1, size-1, -1) ) {
         cout << "\tError: found " << MAX_SIZE+1 <<  " in the array" << endl;
     }
}