//Nonrecursive 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 else
	}//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 CopyArray

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

	//Sort size 1 lists by comparisons to save 1/2 merge calls
	for(int i=0; i<Top; i=i+2) {
		if(A[i] > A[i+1]) {
			tmp = A[i]; A[i]=A[i+1]; A[i+1]=tmp;
		}//end if
	}//end for
	//cout<<"after 1st pass"<<endl;;
	//DisplayData(A, Top);

		//Sort lists of size 2 up and merge
	for(int lsize=2; lsize<=Top; lsize=lsize+lsize) {
		//Merge all adjacent lists of this size
		for(posn=0; posn<Top; posn=posn + lsize+lsize) {
			int TopA; int TopB;
			if(lsize-1<= Top-posn) { //need special tests for odd-sized
				TopA = lsize-1;		//list at end
			}//end if
			else {
				TopA=Top-posn;
			}//end else

			if(posn+lsize+lsize<Top) { //need special tests for odd-sized
				TopB = TopA;		//list at end
			}//end if
			else { TopB = Top-(posn+lsize);
			}//end else

			if((TopA>=0) || (TopB>=0)) {
				//Merge two lists together into tmpArray
				Merge(A+posn, TopA, A+posn+lsize, TopB, tmpArray+posn);

			//Copy tmpArray back to original array
			CopyArray(A, tmpArray, Top);
		}//end for

}//end MergeSort

int main() {
	int TotNumbers; char Resp;

		//Ask user how many numbers to sort

		//Create array new hold specified # of numbers

		//Fill array with random numbers

		//Start the timer
	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

	cout << "Enter Y to Continue"; cin >> Resp;

return 0;
}// end main