//MERGESORT
import java.util.*;

public class MergeSorter
{

	//mergesort subarray from [start,end) end exclusive
	public static void mergesort(int[] array, int start, int end)
	{
		System.out.println("Sorting subarray (" + start +" to "+end+")");
		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);
		mergesort(array,start+size/2,end);
		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)
	{
		System.out.print("Merging ("+a+", "+b+", "+c+") of ");
		printArray(arr);
		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++];
		System.out.print(" Merged sub-array: ");
		printArray(tmp);
	}
	
	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);
		mergesort(array,0,array.length);
		System.out.print("Output: ");
		printArray(array);
	}
	
	public static void printArray(int[] array)
	{
		System.out.print("[");
		for (int i : array)
			System.out.print(i+" ");
		System.out.println("]");
	}
}