public class ExtraStorageMergeSort{
	public static void main(String a[]){
		int i;
		int array[] = {12,9,4,99,120,1,3,10};
		int array1[] = new int[array.length];
		System.out.println("\n\n       RoseIndia\n\n");
		System.out.println("       Extra Strorage Space Merge Sort\n\n");
		System.out.println("Values Before the sort:\n");
		for(i = 0; i < array.length; i++)
			System.out.print( array[i]+"  ");
		System.out.println();
		mergeSort_srt(array,0, array.length-1,array1);
		System.out.print("Values after the sort:\n");
		for(i = 0; i <array.length; i++)
		System.out.print(array1[i]+"  ");
		System.out.println();
		System.out.println("PAUSE");
    }
	
	public static void mergeSort_srt(int array[], int low, int high, int array1[]){
		if(low >= high) {
			return;
		}

		int middle = (low+high) / 2;
		mergeSort_srt(array, low, middle, array1);
        mergeSort_srt(array, middle+1, high, array1);
        int k, t_low = low, t_high = middle+1;
        for(k = low; k <= high; k++)
            if ((t_low <= middle) && ((t_high > high) || (array[t_low] < array[t_high]))) {
				array1[k] = array[t_low++];
			}
            else {
				array1[k] = array[t_high++];
			}
		for(k = low; k <= high; k++) {
			array[k] = array1[k];
		}
	}
}