#include <fstream.h>
#include <string.h>

const int MAX_LENGTH = 35;
typedef char string[MAX_LENGTH];

int intMerge;
int intSort;
string lines[10];
string tmpArray[10];

void Merge(string A[], int F, int Mid, int L) {
	int First1 = F;
	int Last1 = Mid;
	int First2 = Mid + 1;
	int Last2 = L;

	int index = First1;

	for (; (First1<=Last1) && (First2<=Last2); index++) {
		if ( strcmp(A[First1], A[First2]) < 0) {
			strcpy(tmpArray[index], A[First1]);
			First1++;
		}
		else {
			strcpy(tmpArray[index], A[First2]);
			First2++;
		}
	}

	for (; First1<=Last1; First1++, index++) {
		strcpy(tmpArray[index], A[First1]);
	}

	for (; First2<=Last2; First2++, index++) {
		strcpy(tmpArray[index], A[First2]);
	}

	for ( index=F; index<=L; index++ ) {
		strcpy(A[index], tmpArray[index]);
	}
	intMerge++;
}

void MergeSort(string A[], int F, int L) {
	intSort++;
	if ( F < L ) {
		int Mid = (F + L) / 2;
		MergeSort(A, F, Mid);
		MergeSort(A, Mid+1, L);
		Merge(A, F, Mid, L);
	}
}

void main() {
	int line = 0;
	intMerge = 0;
	intSort = 0;

	ifstream InFile("otherSorts.txt");
	while ( InFile.peek() != EOF ) {
		InFile.getline(lines[line++], MAX_LENGTH);
	}
	InFile.close();
	MergeSort(lines, 0, line);
	ofstream OutFile("8.txt");
	for (int i=0; i<10; i++) {
		OutFile << lines[i] << "\n";
	}
	OutFile << "\nMerge Count = " << intMerge << "\n";
	OutFile << "\nMergeSort Count = " << intSort << "\n";
	OutFile.close();
}