package algs.princeton;


public class MergeSort {

	int[] Arr;
	int countMerge;
	//constructor
	MergeSort(int[] A){
		this.Arr=A;
		this.countMerge=0;
	}
	
	public void divide(int[] A, int low, int high){
		if(low==high) return;
		else{
			this.countMerge++;
			int mid=(low+high)/2;
			divide(A, low, mid);
			divide(A, mid+1, high);
			mergeAndSort(A, low, mid, high);
		}
	}
	
	private static void mergeAndSort(int A[], int low, int mid, int high){
		int m=mid-low+1;//num of elements in the first half of Array A
		int n=high-(mid+1)+1; //num of elements in the second half of Array A
		int[] firstHalf=new int [m];
		int[] secondHalf=new int [n];
		
		//extract the first half of already sorted sub array
		for (int i=0; i<m;i++){
			firstHalf[i]=A[low+i];
		}
		//extract the second half of already sorted sub array
		for (int j=0; j<n;j++){
			secondHalf[j]=A[mid+1+j];
		}		
		//sort and merge the two halves together
		int i=0; int j=0;
		while(i<m || j<n){
			if(i>=m){
				A[low++]=secondHalf[j++];
				continue;
			}
			if(j>=n){
				A[low++]=firstHalf[i++];
				continue;
			}
			if(firstHalf[i]<secondHalf[j]){
				A[low++]=firstHalf[i++];
			}else{
				A[low++]=secondHalf[j++];
			}
		}
	}
	
	public void outputArray(int A[]){
		for (int i=0;i<A.length;i++){
			System.out.print(A[i]+", ");
		}
	}
	
	public void outputMergeCounts(){
		System.out.println(" ");
		System.out.println("num of merge executions: "+this.countMerge);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] Array={0,1,3,5,7,9,15,13,11,2,4,6,8,10,14,12};
        MergeSort sort=new MergeSort(Array);
        sort.divide(sort.Arr, 0, sort.Arr.length-1);
        sort.outputArray(sort.Arr);
        sort.outputMergeCounts();
	}

}