package recursion;

/**
 * 鲢㷨
 * @author Administrator
 *
 */
public class DArrayApp {
	public static void main(String[] args) {
		int maxsize = 100;
		Darray arr;
		arr = new Darray(maxsize);
		
		arr.insert(1);
		arr.insert(2);
		arr.insert(9);
		arr.insert(5);
		arr.insert(3);
		arr.insert(4);
		arr.insert(8);
		arr.insert(6);
		arr.insert(7);
		arr.insert(10);
		
		arr.display();
		arr.mergeSort();
		arr.display();
	}
}

class Darray{
	private long[] theArray;
	private int nElems;
	
	public Darray(int max) {
		this.theArray = new long[max];
		this.nElems = 0;
	}
	
	public void insert(int i) {
		this.theArray[this.nElems++] = i;
	}
	
	public void display() {
		for(int j=0;j<this.nElems;j++) {
			System.out.println(this.theArray[j]+" ");
		}
	}
	
	public void mergeSort() {
		long[] workPace = new long[this.nElems];
		recMergeSort(workPace,0,this.nElems-1);
	}
	
	private void recMergeSort(long[] workPace,int lowerBound,int upperBound) {
		if(lowerBound == upperBound) {
			return;
		}
		
		int mid = (lowerBound+upperBound)/2;
		recMergeSort(workPace,lowerBound,mid);
		recMergeSort(workPace,mid+1,upperBound);
		merge(workPace,lowerBound,mid+1,upperBound);
	}
	
	private void merge(long[] workPace,int lowPtr,int highPtr,int upperBound) {
		int j=0;
		int lowerBound = lowPtr;
		int mid = highPtr-1;
		int n = upperBound-lowerBound+1;
		
		while(lowPtr <= mid && highPtr<= upperBound) {
			if(this.theArray[lowPtr] < this.theArray[highPtr])
				workPace[j++] = this.theArray[lowPtr++];
			else
				workPace[j++] = this.theArray[highPtr++];
		}
		
		while(lowPtr <= mid) {
			workPace[j++] = this.theArray[lowPtr++];
		}
		
		while(highPtr <= upperBound) {
			workPace[j++] = this.theArray[highPtr++];
		}
		
		for(j=0;j<n;j++) {
			this.theArray[lowerBound+j] = workPace[j];
		}
	}
}