//MERGESORT
import java.util.*;

public class MergeSorter
{
	public static int depth=0;
	//mergesort subarray from [start,end) end exclusive
	public static void mergesort(int[] array, int start, int end)
	{
		depth++;
		printDepth(' ');
		System.out.print("Sorting subarray from " + start +" to "+end+": ");
		printArray(array,start,end);
		System.out.println();
		
		int size=end-start;
		switch (size)
		{
			case 2:
				testAndSwap(array,start,start+1);
			case 1: //fallthrough
				return;
		}
		
		//split&merge
		mergesort(array,start,start+size/2);
		depth--;
		mergesort(array,start+size/2,end);
		depth--;
		merge(array,start,start+size/2,end);
	}
	
	//switch 2 numbers if not in order
	public static void testAndSwap(int[] a, int f, int s)
	{
		if (a[f] < a[s])
			return;
		int tmp=a[f];
		a[f]=a[s];
		a[s]=tmp;
	}
	
	//merge 2 sub-arrays a - inclusive, c - exclusive
	public static void merge(int[] arr, int a, int b, int c)
	{
		printDepth(' ');
		System.out.print("Merging ");
		printArray(arr,a,b);
		System.out.print(" and ");
		printArray(arr,b,c);
		System.out.println();
		
		int x=a, y=b, tmp[] = new int[c-a], z=0;
		//sort fill temp till 1 subarray is empty
		while (x < b && y < c)
			if (arr[x] > arr[y])
				tmp[z++]=arr[y++];
			else
				tmp[z++]=arr[x++];
		//fill remainder
		while (x < b) tmp[z++]=arr[x++];
		while (y < c) tmp[z++]=arr[y++];
		
		//copy back
		z=0;
		for (int i=a;i<c;i++)
			arr[i]=tmp[z++];
			
		printDepth(' ');
		System.out.print(" Merged sub-array: ");
		printArray(tmp,0,tmp.length);
		System.out.println();
	}
	
	public static void main(String args[])
	{
		int[] array=new int[13];
		
		//initialize random numbers
		Random r = new Random();
		for (int i=0;i<array.length;i++)
			array[i]=r.nextInt(100);
			
		System.out.print("Input:  ");
		printArray(array,0,array.length);
		System.out.println();
		
		mergesort(array,0,array.length);
		
		System.out.print("Output: ");
		printArray(array,0,array.length);
		System.out.println();
	}
	
	public static void printArray(int[] array,int start, int end)
	{
		System.out.print("[");
		for (int i=start;i<end;i++)
			System.out.print(array[i]+" ");
		System.out.print("]");
	}
	
	public static void printDepth(char c)
	{
		for(int i=0;i<depth;i++)
			System.out.print(c);
	}
}