/**
 * A merge sort demonstration algorithm using extra space
 * without recursion.
 *
 * @author Byron Weber Becker  (bwbecker@uwaterloo.ca)
 * @version 	1.0, 2009 Mar 17
 * 
 */
class BottomupMergeSortAlgorithm extends SortAlgorithm
{
	void sort(int a[], int lo, int hi, int scratch[])
	{
		super.updateAllViews(lo, hi);
		
		if (super.stopRequested)
		{
			return;
		}
		
		if (lo >= hi)
		{
			return; /* a[lo] is sorted already   */
		}

		int mid = (lo + hi) / 2;
		sort(a, lo, mid, scratch); /* Sort sublist a[lo..mid]   */
		sort(a, mid + 1, hi, scratch); /* Sort sublist a[mid+1..hi] */

		if (super.stopRequested)
		{
			return;
		}

		// Merge results
		int k, t_lo = lo, t_hi = mid + 1;
		super.lowMarker = lo;
		super.hiMarker = hi;
		for (k = lo; k <= hi; k++)
		{
			/* Merge sorted sublists    */
			super.compares++;
			if ((t_lo <= mid) && ((t_hi > hi) || (a[t_lo] < a[t_hi])))
			{
				scratch[k] = a[t_lo++];
			} else
			{
				scratch[k] = a[t_hi++];
			}
			super.moves++;
			super.activeMarker = k;
			super.updateAllViews();
		}

		for (k = lo; k <= hi; k++)
		{
			a[k] = scratch[k]; /* Copy back to a   */
			super.moves++;
			super.activeMarker = k;
			super.updateAllViews();
		}
	}

	void sort(int a[])
	{
		int n = a.length;
		int work[] = new int[n];
		
		for(int msize = 1; msize < n; msize = msize * 2)
		{
			for(int i=0; i<n; i = i + (msize*2))
			{
				if (super.stopRequested)	return;
				
				int mlo = i;
				int mid = i + msize;
				
				/* odd # of subarrays? */
				if (mid >= n) break;
				
				int mhi = i + (msize * 2) - 1;
				
				/* short last subarray? */
				if (mhi >= n)
					mhi = n-1;
					
				/* Merge a[mlo..mid-1] and a[mid..mhi] */
				int il = mlo;
				int ir = mid;
				int iw = mlo;
				super.updateAllViews(mlo, mhi);
				while (il < mid && ir <= mhi) 
				{
					if (a[il] < a[ir])
						work[iw++] = a[il++];
					else
						work[iw++] = a[ir++];
					super.compares++;
					super.moves++;
					super.activeMarker = iw;
					super.updateAllViews();
				}
				while (il < mid) 
				{	work[iw++] = a[il++];
					super.compares++;
				}
				while (ir <= mhi) 
				{	work[iw++] = a[ir++];
					super.compares++;
				}
				
				// Copy back to a
				for(iw = mlo; iw <= mhi; iw++)
				{	a[iw] = work[iw];
					super.moves++;
					super.activeMarker = iw;
					super.updateAllViews();
				}
			}
		}
		
		super.updateAllViews(-1, -1);
	}
}