import java.util.Random;


public class MergeSortEtd {

	public static void main(String[] args) {
		int lg;
		if (args.length < 1) 
			lg = 200;
		else lg = Integer.parseInt(args[0]);
		Random gen = new Random();

		// just create two arrays for test
		int[] t1 =new int[lg];
		int[] t2 =new int[lg];
		for (int i = 0;i<lg;i++){
			t1[i]= gen.nextInt(99);
			t2[i]= t1[i];
		}

		mergeSort(t1, 0, t1.length-1);
		System.out.print("Sorted: ");
		for (int i = 0; i <t1.length; i++) 
			System.out.print(t1[i] + " - ");
		System.out.println();


		mergeSortParallel(t2, 0, t2.length-1);
		System.out.print("Sorted: ");
		for (int i = 0; i <t2.length; i++) 
			System.out.print(t2[i] + " - ");
		System.out.println();
	}


	private static void mergeSortParallel(int tab[],int start,int end)  {
		// TODO
	}

	private static void mergeSort(int tab[],int start,int end) {
		if (start!=end){
			int middle=(end+start)/2;
			mergeSort(tab,start,middle);
			mergeSort(tab,middle+1,end);
			merge(tab,start,middle,end);
		}
	}

	/*
	 * Merge the given array
	 * Assume it is split in two ordered sub-arrays (tab1: from start to middle, tab2: from middle+1 to end)
	 */
	private static void merge(int tab[],int start,int middle,int end) {
		//copy the first tab in a temporary array
		int tab1[]=new int[middle-start+1];
		for(int i=start;i<=middle;i++)
			tab1[i-start]=tab[i];

		int start2=middle+1;
		int iter1=start;
		int iter2=start2;

		for(int i=start;i<=end;i++){        
			if (iter1==start2) 
				//we are done with tab1, thus all elements are ordered
				break;       
			else if (iter2==(end+1)) { 
				//we are done with tab2, we just need to add the remaining elements from tab1
				tab[i]=tab1[iter1-start]; 
				iter1++;
			} else if (tab1[iter1-start]<tab[iter2]){
				//insert the element of tab1
				tab[i]=tab1[iter1-start]; 
				iter1++;
			}else {
				//insert the element of tab2
				tab[i]=tab[iter2]; 
				iter2++;
			}
		}
	}
}