#include <iostream>

using namespace std;

const size_t ARRAY_SIZE{10};
const size_t ELEMENT_SIZE{10000};

void MergeSort(int data[], size_t low, size_t high);
void PrintArray(int data[], size_t low, size_t high);
void SearchList(int data[], size_t size);
size_t BinarySearch(int data[], int low, int high,int key);

int main() {
    size_t i;
    int data[ARRAY_SIZE];

    srand(time(nullptr));
    // fill it
    for(i = 0; i < ARRAY_SIZE; ++i) {
        data[i] = rand() % ELEMENT_SIZE;
    }

    PrintArray(data, 0, ARRAY_SIZE-1);

    MergeSort(data, 0, ARRAY_SIZE -1);

    cout << endl << endl;
    PrintArray(data, 0, ARRAY_SIZE-1);

    SearchList(data, ARRAY_SIZE);

    return 0;
}

bool Continue() {
    char keepGoing{'x'};

    while (keepGoing != 'y' and keepGoing != 'n') {
        cout << "Do you want to search the list? (y/n)" ;
        cin >> keepGoing;
    }


    return keepGoing == 'y';
}

void SearchList(int data[], size_t size){
    int value;
    size_t pos;

    while (Continue()) {
       cout << "Enter a value to find ";
       cin >> value;
       if ( (pos = BinarySearch(data, 0, size-1, value)) == ARRAY_SIZE) {
           cout << value << " is not in the list." << endl;
       } else {
           cout << value << " is at position " << pos << "."  << endl; 
       }
    }

}

size_t BinarySearch([[maybe_unused]] int data[],[[maybe_unused]]  int low, [[maybe_unused]] int high, [[maybe_unused]] int key){

       int mid{(low+high)/2};

       if (low > high) {
           return  ARRAY_SIZE;
       } else if (data[mid] == key) {
           return static_cast<size_t>(mid);
       } else if (data[mid] < key) {
           return BinarySearch(data,mid+1, high,key);
       } else {
           return BinarySearch(data,low, mid-1,key);
       }
}


void Merge(int data[], size_t low, size_t mid, size_t high) {
    int tmp[ARRAY_SIZE];

    size_t lowPos{low};
    size_t highPos{mid+1};
    size_t destPos(low);

    // merge the two
    while(lowPos <= mid  and highPos <= high) {
       if(data[lowPos] < data[highPos]) {
          tmp[destPos] = data[lowPos];
          ++lowPos;
       } else {
          tmp[destPos] = data[highPos];
          ++highPos;
       }
       ++destPos;
    }

    // only one of these will run
    while (lowPos <= mid) {
       tmp[destPos] = data[lowPos];
       ++lowPos;
       ++destPos;
    }

    while (highPos <= high) {
       tmp[destPos] = data[highPos];
       ++highPos;
       ++destPos;
    }

    for( destPos = low; destPos <= high; ++destPos) {
        data[destPos] = tmp[destPos];
    }
}

void PrintArray(int data[], size_t low, size_t high){
   size_t i;

   for(i = low; i<= high; ++i) {
      cout << data[i] << endl;
   }
   cout << endl;
}

void MergeSort(int data[], size_t low, size_t high){
    size_t mid{(low+high)/2};
    if (low < high) {
        MergeSort(data,low,mid);
        MergeSort(data,mid+1, high);
        Merge(data, low, mid, high);
    }
}