/*
 * Instituto Superior de Engenharia do Porto
 *
 * Estruturas de Informação
 *
 * 2000/2001
 *
 * (C) Paulo Sousa
 *
 * ------------------------------------------
 *
 * Trabalho nº 1
 *
 *	algoritmo mergesort
 *
 */


/**

  descrição em http://www.people.fas.harvard.edu/~toub/cs50/sorting/merge.html

  best		O(n log n) 
  worst		O(n log n) 
  expected	O(n log n) 
  average	O(n log n) 

 **/


#ifndef __MERGESORT_INC__
#define __MERGESORT_INC__


template <class T>
class MergeSort
{
	static void mergesort_1(T A[], int low, int high);
	static void mergesort_2(T A[], int low, int high);
	static void merge_3(T A[], T temp[], int left, int right, int mid);
	static void merge_4(T A[], int left, int mid, int right, T temp[]);

public:
	static void mergesort_1(T A[], int nSize);

	// array auxiliar
	static void mergesort_2(T A[], int nSize);

	// versão iterativa
	static void mergesort_3(T A[], int nSize);

	// versão iterativa (botton-up)
	static void mergesort_4(T A[], int nSize);
};


//----------------------------------------------------------
//
//				I M P L E M E N T A Ç Ã O
//
//----------------------------------------------------------


/**
 * A merge sort demonstration algorithm
 * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
 *
 * @author Jason Harrison@cs.ubc.ca
 * @version 	1.1, 12 Jan 1998
 */
template <class T>
void MergeSort<T>::mergesort_1(T A[], int low, int high)
{
	int lo = low;
	int hi = high;

	if (lo >= hi)
		return;

	int mid = (lo + hi) / 2;

	/*
	*  Partition the list into two lists and sort them recursively
	*/
	mergesort_1(A, lo, mid);
	mergesort_1(A, mid + 1, hi);

	/*
	*  Merge the two sorted lists
	*/
	int end_lo = mid;
	int start_hi = mid + 1;
	while ((lo <= end_lo) && (start_hi <= hi)) 
	{
		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		if (A[lo] < A[start_hi]) 
			lo++;
		else 
		{
			/*  
			 *  a[lo] >= a[start_hi]
			 *  The next element comes from the second list, 
			 *  move the a[start_hi] element into the next 
			 *  position and shuffle all the other elements up.
			 */
			int temp = A[start_hi];		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			for (int k = start_hi - 1; k >= lo; k--) 
			{
				A[k+1] = A[k];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			}
			A[lo] = temp;	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			lo++;
			end_lo++;
			start_hi++;
		}
	}
}

template <class T>
void MergeSort<T>::mergesort_1(T A[], int nSize)
{
	if (nSize < 2)
		return;

	mergesort_1(A, 0, nSize-1);
}


//
//-------------------------------------------------
//



/**
 * A MergeSort demonstration algorithm
 * MergeSortAlgorithm.java
 *
 * @author Patrick Morin
 */
template <class T>
void MergeSort<T>::mergesort_2(T A[], int lo, int hi)
{
	// Base case
	if(lo == hi)
		return;

	// Recurse
	int length = hi-lo+1;
	int pivot = (lo+hi) / 2;
	mergesort_2(A, lo, pivot);
	mergesort_2(A, pivot+1, hi);

	// Merge
	T* working = new T[length];
	for(int i = 0; i < length; i++)
	{
		working[i] = A[lo+i];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
	}
	int m1 = 0;
	int m2 = pivot-lo+1;
	for(i = 0; i < length; i++) 
	{
		if(m2 <= hi-lo) 
		{
			if(m1 <= pivot-lo) 
			{
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				if(working[m1] > working[m2]) 
				{
					A[i+lo] = working[m2++];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				}
				else 
				{
					A[i+lo] = working[m1++];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				}
			}
			else 
			{
				A[i+lo] = working[m2++];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			}
		}
		else 
		{
			A[i+lo] = working[m1++];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		}
	}
	delete [] working;
}


template <class T>
void MergeSort<T>::mergesort_2(T A[], int nSize)
{
	if (nSize < 2)
		return;

	mergesort_2(A, 0, nSize-1);
}



//
//-------------------------------------------------
//


//
// http://www.math.grin.edu/~wislocki/302/assignment4/mergesort.c
//
template <class T>
void MergeSort<T>::mergesort_3(T A[], int nSize)
{
	if(nSize < 2)
		return;

	T* temp = new T[nSize];

	for(int i = 2; i <= nSize; i*=2) 
	{
		for (int j = 0; j < nSize; j+=i) 
		{
			if (j+i-1 <= nSize-1)
				merge_3(A, temp, j, j+i-1, -1);     
			else
				//merge_3(A, temp, j, nSize-1, j+i/2-1);
				merge_3(A, temp, j, nSize-1, min(j+i/2-1, nSize-1));
		}
	}

	/* Check to see if we need to merge one last time. */
	double base2 = log2(nSize);

	int closest = (int)pow(2.0, (double)((int)base2));

	if(base2 != (double)((int)base2))
		merge_3(A, temp, 0, nSize-1, closest-1);

	delete [] temp;
}

template <class T>
void MergeSort<T>::merge_3(T A[], T temp[], int left, int right, int mid)
{
	/* Check to see if we need to calculate mid here or not. */
	if(right - left < 1)
		return;

	if (mid == -1)
		mid = (left + right) / 2;

	for (int j = mid+1; j > left; j--)
	{
		temp[j-1] = A[j-1];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
	}

	for (int k = mid; k < right; k++)
	{
		temp[right+mid-k] = A[k+1];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
	}

	for (int i = left; i <= right; i++)
	{
		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		A[i] = (temp[j] < temp[k]) ? temp[j++] : temp[k--];		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
	}
}


//
//-------------------------------------------------
//


//
// http://www.people.fas.harvard.edu/~toub/cs50/sorting/bumerge.c
//
/* Sort array a[] of n integers using bottom-up merge sort */
template <class T>
void MergeSort<T>::mergesort_4(T A[], int nSize)
{
	if (nSize < 2)
		return;

	T* temp = new T[nSize];

	for (int N = 1; N < nSize; N *= 2) 
	{ 
		int r = 0;
		for (int l = 0; l < nSize; l = r+1) 
		{
			r = l + 2*N - 1;
			if (r >= nSize) 
			{ 
				//merge_4(A, l, l+N-1, nSize, temp);
				merge_4(A, l, l+N-1, nSize-1, temp);
				if (l > 1) 
					//merge_4(A, l-2*N, l-1, nSize, temp);
					merge_4(A, l-2*N, l-1, nSize-1, temp);
			} 
			else 
			{
				merge_4(A, l, l+N-1, r, temp);
			}
		}
	}

	delete [] temp;
} 

template <class T>
void MergeSort<T>::merge_4(T A[], int l, int m, int r, T b[])
{
	int i = l;
	int j = m+1; 
	
	for (int k = l; k <= r; k++) 
	{
		if (i > m) 
		{
			b[k] = A[j++];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		}
		else if (j > r) 
		{
			b[k] = A[i++];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		}
		else
		{
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			b[k] = A[i] < A[j] ? A[i++] : A[j++];
		}
	} //???
	    for (k = l; k <= r; k++) 
		{
			A[k] = b[k];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		}
	//} 
}



#endif