/*
 * Created on Aug 4, 2005
 * 
 * CPS 006 - Summer 05
 * Sam Slee
 * Merge.java
 * 
 * 
 */

/**
 * @author sslee
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class Merge {

	//---------------------------------------------------------------------------------
	// Demonstrates the Merge Sort algorithm.
	public static void main(String[] args) {
		int[] random = {8, 36, 27, 25, 15, 13, 19, 5, 9, 34, 10, 11, 7, 
				33, 6, 30, 14, 3, 18, 22, 32, 16, 1, 20, 24, 
				26, 2, 4, 17, 23, 29, 31, 12, 21, 28, 35};

		int[] reverse = {36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25,
				24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13,
				12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
		
		int[] input = random;
		int goal = 0;
		
		System.out.println("Array entries: ");
		for(int i=0; i<input.length; i++)
			System.out.print(input[i]+" ");
		
		System.out.println("\n\nSorting with Merge Sort \n");
		
		mergeSort(input, 0, input.length-1);
		
		System.out.println("Sorted array entries: ");
		for(int i=0; i<input.length; i++)
			System.out.print(input[i]+" ");
	}
	
	
	//---------------------------------------------------------------------------------
	// Sorts the desired entries in the input[] array: input[startIndex .. endIndex]
	// Entries at other indexes are unaffected.
	// Sorts using Merge Sort - O(n lg n) time.
	public static void mergeSort (int[] input, int startIndex, int endIndex){
		
		// make sure that there's more than 1 entry left in this subsection to sort
		// (1 entry by itself is already sorted)
		if(startIndex < endIndex){
			
			// find the middle of our subsection
			int middle = (endIndex + startIndex)/2;
			
			// recursively sort each half of our subsection
			mergeSort(input, startIndex, middle);
			mergeSort(input, middle+1, endIndex);
			
			// merge our those 2 halves together into a single sorted subsection
			merge(input, startIndex, endIndex, middle);
		}
	}
	
	
	//---------------------------------------------------------------------------------
	// merge the entries in the array in the two sorted subsections
	// input[startIndex .. middle] and input[middle+1 .. endIndex]
	public static void merge(int[] input, int startIndex, int endIndex, int middle){
		// create 2 holder arrays and initialize those arrays
		int[] top = new int[middle - startIndex + 1];
		int[] bottom = new int[endIndex - middle];
		int i, j, k;
		
		// initializing...
		for(i=0, j=startIndex; i < top.length; i++, j++)
			top[i] = input[j];
		
		// initializing...
		for(i=0, j=middle+1; i < bottom.length; i++, j++)
			bottom[i] = input[j];
		
		// keep taking the next smallest entry off the "remaining"
		// spots in each array
		for(i=0, j=0, k=startIndex; i<top.length && j<bottom.length; ){
			if(top[i] < bottom[j])
				input[k++] = top[i++];
			else
				input[k++] = bottom[j++];
		}
		
		// one of the arrays is empty, the other has at least one item left
		// So, one of these loops will run 0 times
		// the other loop will move those remaining entries into the big "input" array
		while(i < top.length)
			input[k++] = top[i++];
		while(j < bottom.length)
			input[k++] = bottom[j++];
		
	}
}