//
// Merge sort
//
// Merge sort sorts the elements in the part of the array A that
// lie between position first and position last.  It is a recursive 
// sort that works by splitting that part the array into two halves,
// recursively sorting each half, and then merging the two sorted halves
// into a sorted whole.
//
// The recursion bottoms out when merge sort is asked to sort only one 
// element.
//

//
// The merge function
//
// Merge combines two sorted subarrays into a single sorted array.  
// The first subarray consists of the elements from A[first] to A[middle].
// The second consists of the elements from A[middle+1] to A[last].  
//
// It begins by dynamically allocating memory for a copy array.  It enters 
// the first while loop, which uses leftIndex to keep track of which element 
// is to be copied next from the first subarray and rightIndex to keep track
// of which element is to be copied from the second subarray.  
//
// In the while loop, it compares an element in the left subarray to one in 
// the right subarray and copies the smaller one to the copy array.
//
// Eventually, one of the subarrays has been completely copied and the while
// loops at the bottom of the function copy the remaining elements from the 
// other subarray.
//
// At the very end, the copy array is copied back into A and its memory is 
// deallocated.
//

void merge(int A[], int first, int middle, int last)
{
	int leftIndex, rightIndex, copyIndex;
	int *copy;

	// Allocate space for an array to copy into.	
	copy = new int[last + 1];
	
	leftIndex = first;
	rightIndex = middle + 1;
	copyIndex = first;
	
	// While there are elements in both subarrays, copy
	// the smaller of the first elements of each subbary 
	// into the copy array.

	while (leftIndex <= middle && rightIndex <= last) {
		if (A[leftIndex] < A[rightIndex]) {
			copy[copyIndex] = A[leftIndex];
			leftIndex++;
		}
		else {
			copy[copyIndex] = A[rightIndex];
			rightIndex++;
		}
		copyIndex++;
	}

	// If the right subarray was the first to be 
	// copied, now copy the rest of the left subarray.

	while (leftIndex <= middle) {
		copy[copyIndex] = A[leftIndex];
		leftIndex++;
		copyIndex++;
	}

	// If the left subarray was the first to be 
	// copied, now copy the rest of the right subarray.

	while(rightIndex <= last) {
		copy[copyIndex] = A[rightIndex];
		rightIndex++;
		copyIndex++;
	}

	// Copy the array back to A.

	for (copyIndex = first; copyIndex <= last; copyIndex++) {
		A[copyIndex] = copy[copyIndex];
	}

	delete [] copy;

	return;

}

void mergeSort(int A[], int first, int last)
{
	int middle;
	
	// If there is only one element to sort, do nothing.

	if (first == last) {
		return;
	}
	// Otherwise, split the array in the middle, recursively
	// sort each half, and then combine the sorted halves using
	// merge.

	else {
		middle = (first + last) / 2;
		mergeSort(A, first, middle);
		mergeSort(A, middle+1, last);
		merge(A, first, middle, last);
		return;
	}
}