/* Merge Sort program */

#include <stdlib.h>
#include <iostream.h>
#include <lvpvector.h>
#include <lvprandom.h>

using namespace std;	// October 5, 2001

typedef int ItemType;
typedef lvpvector<ItemType> ArrayType;

//--------------------------------------------------------------------------------
void Merge(ArrayType &A, int Start, int Mid, int End)
/*	Merges two sorted portions of A
	Pre: A[Start..Mid] is sorted, A[Mid+1..End] is sorted
	Start <= Mid <= End
	Post: A[Start..End] is sorted	                              */
{
	ArrayType Temp(A.length());

	int P1 = Start; int P2 = Mid+1;    // Indexes of current item in each sublist
	int Spot = Start;    // Present location in Temp
	while (!(P1>Mid && P2>End)) {
		if ((P1>Mid) || ((P2<=End) && (A[P2]<A[P1]))) {
			Temp[Spot] = A[P2];
			P2++;
		}
		else {
			Temp[Spot] = A[P1];
			P1++;
		}
		Spot++;
	}
	// Copy values from Temp back to A 
	for (int i=Start; i<=End; i++)
		A[i] = Temp[i];
}
//--------------------------------------------------------------------------------
void MergeSort(ArrayType &A, int Start, int End)
/*	Sorts A[Start..End] elements from low to high
	Pre: Start, End >= 0
	Post: Elements A[Start..End] are sorted from low to high */
{
	if (Start < End) {
		int Mid = (Start+End)/2;
		MergeSort(A, Start, Mid);
		MergeSort(A, Mid+1, End);
		Merge(A, Start, Mid, End);
	}
}
//--------------------------------------------------------------------------------
void LoadRandomArray(ArrayType &A, int Size)
/*	Fills array A with Size random values in the range 0..999 */
{
	const int MaxValue = 999;
	A.resize(Size);
	for (int i=0; i<Size; i++)
		A[i] = lvprandom(MaxValue+1);
}
//--------------------------------------------------------------------------------
void DisplayArray(const ArrayType &A)
/*	Displays the items of A, with field width of 5, 10 per line */
{
	for (int i=0; i<A.length(); i++) {
		cout.width(5); cout << A[i];
		if ((i+1)%10 == 0)
			cout << endl;
	}
	cout << endl;
}
//--------------------------------------------------------------------------------
void Sort (ArrayType &A)
/*	Sorts array A from low to high */
{
	MergeSort(A, 0, A.length()-1);
}
//--------------------------------------------------------------------------------
int main()
{
	randomize();
	ArrayType Sample;
	const int SampleSize = 20;
	LoadRandomArray(Sample, SampleSize);
	DisplayArray(Sample);
	Sort(Sample);
	DisplayArray(Sample);
	return(0);
}