//---------------------------------
// MergeSort.Java
// Written By: Russell Schwager
//             russells@jhu.edu
// February 3, 1997
//---------------------------------

// Insert Copyright comments

//------------------ BEGIN UI CODE ----------------
import java.awt.Graphics;
//------------------ END UI CODE ------------------

// Merge Sort algorithm

public class MergeSort extends SortAlgorithm
{										   
	//---------BEGIN UI CODE----------------------
	SortPanel panel;
	int demoFrom, demoTo, demoMid;

	public MergeSort(SortableObject anObject, SortPanel panel)
	{ // Constructor

		super(anObject);
		algorithmName = "Merge-Sort";
		this.panel = panel;
	}

	public void init()
	{
		objectToSort.setStatus(false);

	}

	public void demoSort() throws Exception
	{
		if (!objectToSort.getStatus())
		{
			demoSort(objectToSort, 0, objectToSort.size() - 1);
			objectToSort.setStatus(true);
		}
	}

	private void demoSort(SortableObject anObject, 
		int from, int to)
	{
	
		int mid;

		panel.pause();
		if (from < to)
		{
			mid = (int)(Math.floor((from + to) / (double)2));
			sort(anObject, from, mid);
			sort(anObject, mid + 1, to);
			panel.pause();
			merge(anObject, from, to, mid);
			panel.pause();
		}
	}

	public void drawMiscInfo(Graphics g)
	{
		// do nothing for now
		int i = 3;
	}
	
	//---------END UI CODE----------------------

	public MergeSort(SortableObject anObject)
	{ // Constructor

		super(anObject);
		algorithmName = "Merge-Sort";
	}

	public MergeSort()
	{ // Default Constructor

		super();
		algorithmName = "Merge-Sort";
	}

	public void sort()
	{
		if (!objectToSort.getStatus())
		{
			sort(objectToSort, 0, objectToSort.size() - 1);
			objectToSort.setStatus(true);
		}
	}

	
	private void sort(SortableObject anObject, 
		int from, int to)
	{
	
		int mid;

		if (from < to)
		{
	
			mid = (int)(Math.floor((from + to) / (double)2));
			sort(anObject, from, mid);
			sort(anObject, mid + 1, to);
			merge(anObject, from, to, mid);
		}
	}

	private void merge(SortableObject anObject, 
		int from, int to, int mid)
	{ // Merges two sorted lists contained in the Sortable Object

		int i, subListFrom = from, subListTo = mid + 1;
		Object scratch[] = new Object[anObject.size()];

		// Merge two sorted sublists using a scratch array
		for (i = from; i <= to; i++) 
			if ((subListFrom <= mid) && 
			   ((subListTo > to) || 
			    (anObject.compare(subListFrom, subListTo) == anObject.at(subListTo))))
				scratch[i] = anObject.at(subListFrom++);
			else
				scratch[i] = anObject.at(subListTo++);

		// Copy values stored in scratch array back
		for (i = from; i <= to; i++) 
			anObject.setElementAt(scratch[i], i); 

	}
}