import java.util.Arrays;

class Arrays_Merge{
    private int[] arrays;
    private int curNum;
    //int[] workSpace;
 
    public Arrays_Merge(int max) {         //建立一个max长度的空数组
        super();
        arrays = new int[max];
        curNum = 0;
    }
     
    public void insert(int value){                  //往空的数组里面增加元素
        arrays[curNum] = value;
        curNum++;
    }
     
    public void display(){                                  //显示数组
        System.out.println(Arrays.toString(arrays));
    }
    
    public void mergeSort(){
    	int[] arrays = new int[curNum];
    	recMergeSort(arrays, 0, curNum-1);
    }
    
    public void recMergeSort(int[] workSpace,int lowerBound,int upperBound){
    	if(lowerBound == upperBound)
    		return;
    	else
    	{
    		int mid = (lowerBound+upperBound)/2;
    		recMergeSort(workSpace,lowerBound,mid);
    		recMergeSort(workSpace,mid+1,upperBound);
    		merge(workSpace,lowerBound,mid+1,upperBound);
    		System.out.println("mid="+mid);
    	}
    }
     
    public void merge(int[] workSpace,int lowPtr,int highPtr,int upperBound){
    	int j=0;
    	int lowerBound = lowPtr;
    	int mid = highPtr-1;
    	int n = upperBound-lowerBound+1;
    	
    	while(lowPtr<=mid &amp;&amp; highPtr<=upperBound){
    		if(arrays[lowPtr]<arrays[highPtr]){			//如果后面的小，就先放进新的数组中
    			workSpace[j++] = arrays[lowPtr++];		//如果运行第一行，就运行下面的第二个
    			System.out.println("1lowPtr="+(lowPtr-1)+" "+workSpace[j-1]);
    		}else{
    			workSpace[j++] = arrays[highPtr++];	//如果运行第二行，就运行下面的第一个
    			System.out.println("1highPtr="+(highPtr-1)+" "+(j-1)+"="+workSpace[j-1]);
    		}
    	}
    	
    	while(lowPtr<=mid){						//以下两个只可能运行一个
    		workSpace[j++] = arrays[lowPtr++]; 
    		System.out.println("lowPtr="+(lowPtr-1)+" "+workSpace[j-1]);
    	}
    	
    	while(highPtr<=upperBound){
    		workSpace[j++] = arrays[highPtr++];
    		System.out.println("highPtr="+(highPtr-1)+" "+workSpace[j-1]);
    	}
    	
    	for(j=0;j<n;j++){
    		arrays[lowerBound+j] = workSpace[j];
    	}
    }
}

public class MergeSort {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		int maxSize=10;
		Arrays_Merge arr;
		arr = new Arrays_Merge(maxSize);
		arr.insert(9);
		arr.insert(8);
		arr.insert(7);
		arr.insert(6);
		arr.insert(5);
		arr.insert(4);
		arr.insert(3);
		arr.insert(2);
		arr.insert(1);
		arr.display();
		arr.mergeSort();
		arr.display();
	}

}