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();
  }

}