package test;

public class IterativeMergeSort {

	public static void sort(Comparable[] a)
	{
		//sortedSize is the size of sub-arrays that are sorted
		//if we think of the array as sub-arrays of single elements, it is sorted at that level
		for(int sortedSize = 1; sortedSize < a.length; sortedSize *= 2)
		{
			System.out.print(sortedSize + " ");
			testmain.outy(a);
			//merges all adjacent sub-arrays of size sortedSize
			for(int leftIndex = 0; leftIndex < a.length - sortedSize; leftIndex += 2* sortedSize)
				
				//any merge will work
				//the int arguments define the logical separation of the two sub-arrays being passed in
				merge(a, leftIndex, leftIndex + sortedSize - 1, Math.min(leftIndex + sortedSize + sortedSize - 1, a.length - 1));
		}
	}
	
	private static void merge(Comparable[] a, int leftIndex, int midIndex, int rightIndex)
	{
		//temporary array we need for auxiliary storage
		//uses more memory than it needs to make indices match
		Comparable[] leftArray = new Comparable[rightIndex + 1];
		Comparable[] rightArray = new Comparable[rightIndex + 1];
		
		//the two sorted arrays passed in are logically separated
		//physically separate them into 2 arrays
		for(int w = leftIndex; w <= midIndex; ++w)
			leftArray[w] = a[w];
		for(int z = midIndex + 1; z <= rightIndex; ++z)
			rightArray[z] = a[z];
		
		//preconditions: the 2 merging arrays must be sorted
		assert isSorted(leftArray, leftIndex, midIndex);
		assert isSorted(rightArray, midIndex + 1, rightIndex);

		int leftArrayIndex = leftIndex;//access index of the (sorted) left array
		int rightArrayIndex = midIndex + 1;//access index of the (sorted) right index
		
		//the merge
		//loop through every element of the array passed in
		//replacing with the correctly ordered element from the auxiliary array
		while(leftIndex <= rightIndex)
		{
			if (leftArrayIndex > midIndex) 
				a[leftIndex++] = rightArray[rightArrayIndex++];
			else if (rightArrayIndex > rightIndex) 
				a[leftIndex++] = leftArray[leftArrayIndex++];
			else if (rightArray[rightArrayIndex].compareTo(leftArray[leftArrayIndex]) < 0) 
				a[leftIndex++] = rightArray[rightArrayIndex++];
			else 
				a[leftIndex++] = leftArray[leftArrayIndex++];
		}
	}
	
	private static boolean isSorted(Comparable[] a, int leftIndex, int rightIndex)
		{
			for(int i = leftIndex; i < rightIndex; ++i)
				if(a[i].compareTo(a[i + 1]) > 0) return false;
			return true;
		}
}