//Recursive mergesort

#include <iostream>
#include <ctime>
using namespace std;

//Generate a random data set of size TopIndex+1 to sort
void GetData(int dataArray[], int TopIndex) {
	srand(time(NULL));
	for(int i=0; i<=TopIndex; i++) {
		dataArray[i] = rand();
	}//end for
}//end GetData

//Display the data set
void DisplayData(int dataArray[], int TopIndex) {
	for(int i=0; i<=TopIndex; i++) {
		cout << dataArray[i] << endl;
	}//end for
}//end DisplayArray

void Merge(int A[], int TopA, int B[], int TopB, int C[]) {
	bool fini=false;
	int ptrA=0; int ptrB=0; int ptrC=0;

	while(!fini) {
		if(ptrA>TopA) {	//if past end of A array
						//copy rest of array B to C

		if(ptrB>TopB) { //if past end of B array
						//copy rest of array A to C

			 //if A's current element <= B's current element
				//copy A's current to C.
		//else B's current element < A's current element
			//copy B's current to C.
	}//end while
}//end Merge

void CopyArray(int A[], int B[], int TopIndex) {
	for( int i=0; i<=TopIndex; i++) {
		A[i] = B[i];
	}//end for
}//end Copy Array

void MergeSort(int A[], int Top) {
	//Create a scratch pad array to merge into
	int* tmpArray = new int[Top+1];

	if(Top>0) { //if more than one element
		//Sort 1st half of array
		MergeSort(A, Top/2);
		//Sort second half of array
		MergeSort(A+Top/2+1, Top-Top/2-1);

		//Merge the two halves together into tmpArray
		Merge(A, Top/2, A+Top/2+1, Top-Top/2-1, tmpArray);
		//Copy tmpArray back to original array
		CopyArray(A, tmpArray, Top);
		delete[] tmpArray;
	}//end if
}//end MergeSort

int main() {
	int Topindex=15; int TotNumbers; char Resp;

		//Ask user how many numbers to sort
		//Create array new hold specified # of numbers
	int* dataArray = new int[TotNumbers];

		//Fill array with random numbers
	cout << "Display numbers in array? ";
	cin >> Resp;
	if(Resp=='y' || Resp=='Y') {
		DisplayData(dataArray, TopIndex);
	}//end if

	long ClockStart = clock();	//Mark the start time

		//Call MergeSort to sort numbers
	MergeSort(dataArray, TopIndex);

	long ClockEnd = clock(); //Check the end time
	cout << "Clock Start=" << ClockStart << endl;
	cout << "Clock End=" << ClockEnd << endl;
	cout << "Difference =" << ClockEnd-ClockStart << endl;
	cout << "Data Sorted " << endl;

	cout << "Display sorted numbers? ";
	cin >> Resp;
	if(Resp=='y' || Resp=='Y') {
		DisplayData(dataArray, TopIndex);
	}//end if
return 0;
}// end main