public class MergeSort {

  private int[] theArray = { 3, 1, 2, 4};

  private int size;

  private int[] workspace;
  
  public MergeSort( ) {
    
  }

  public MergeSort(int size) {
    this.size = size;
  }

  public void mergeIt() {
    workspace = new int[theArray.length];
    recMerge(workspace, 0, theArray.length-1);
  }

  public void recMerge(int[] workspace, int begin, int end) {
    if (begin == end)
      return;

    int mid = (begin + end) / 2;
    recMerge(workspace, begin, mid);
    recMerge(workspace, mid + 1, end);
    merge(workspace, begin, mid + 1, end);

  }

  public void merge(int[] workspace, int begin, int up, int end) {
//就是这个j，老是莫名其妙的增加
    int j = 0;
    int n = end-begin+1;
    int mid = up-1;
    
    while (begin <= mid && up <= end)
      if (theArray[begin] < theArray[up])
        workspace[j++] = theArray[begin++];
      else
        workspace[j++] = theArray[up++];

    while (begin <= mid) 
      workspace[j++] = theArray[begin++];

    while (up <= end)
      workspace[j++] = theArray[up++];
    
    for( j=0; j<n; j++) 
      theArray[begin+j]=workspace[j];
  }

  public void output() {
    for (int i : theArray)
      System.out.println(i);

  }

  /**
   * @param args
   */
  public static void main(String[] args) {
    MergeSort s = new MergeSort();
    s.mergeIt();
    s.output();
  }

}

    /**
     * QuickOrder
     * @param num
     */
    public void doQuickOrder(int[] num) {
        if (num.length > 1) {
            //设置无序列的第一个元素为中间参考元素
              int middle = num[0];
            
            //----得到比中间元素小的元素的个数----begin//
            int minNum = 0;
            for (int i = 1; i < num.length; i++) {
                if (num[i] < num[0]) {
                    minNum++;
                }
            }
            //----得到比中间元素小的元素的个数----end//
            
            //----分别创建比中间元素小的元素序列和比中间元素大(包括等于)的元素序列并赋值begin//
            int[] minArr = new int[minNum];
            int[] maxArr = new int[num.length - minNum - 1];
            int numMinArr = 0;
            int numMaxArr = 0;
            for (int i = 1; i < num.length; i++) {
                if (num[i] < num[0]) {
                    minArr[numMinArr] = num[i];
                    numMinArr++;
                } else {
                    maxArr[numMaxArr] = num[i];
                    numMaxArr++;
                }
            }
            //----分别创建比中间元素小的元素序列和比中间元素大(包括等于)的元素序列并赋值end//
            
            //----对小序列和大序列分别递归执行快速排序begin//
            doQuickOrder(minArr);
            doQuickOrder(maxArr);
            //----对小序列和大序列分别递归执行快速排序end//
            
            //----将最终结果按照 小序列+中间元素+大序列 的顺序合并begin//
            for (int i = 0; i < minNum; i++) {
                num[i] = minArr[i];
            }
            num[minNum] = middle;
            for (int i = 0; i < maxArr.length; i++) {
                num[minNum + 1 + i] = maxArr[i];
            }
            //----将最终结果按照 小序列+中间元素+大序列 的顺序合并end//
        }
    }