算法规则： 像快速排序一样，由于归并排序也是分治算法，因此可使用分治思想：

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2.设定两个指针，最初位置分别为两个已经排序序列的起始位置 

3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 

4.重复步骤3直到某一指针到达序列尾 

5.将另一序列剩下的所有元素直接复制到合并序列尾

1 public void mergeSort(int[] ints, int[] merge, int start, int end)  2   { 3       if (start >= end) return; 4        5       int mid = (end + start) >> 1; 6        7       mergeSort(ints, merge, start, mid); 8       mergeSort(ints, merge, mid + 1, end); 9 10       merge(ints, merge, start, end, mid);11 12   }13   14   private void merge(int[] a, int[] merge, int start, int end,int mid) 15   {16       int i = start;17       int j = mid+1;18       int pos = start;19       while( i <= mid || j <= end ){20           if( i > mid ){21               while( j <= end ) merge[pos++] = a[j++];22               break;23           }24           25           if( j > end ){26               while( i <= mid ) merge[pos++] = a[i++];27               break;28           }29           30           merge[pos++] = a[i] >= a[j] ? a[j++] : a[i++];31       }32       33       for (pos = start; pos <= end; pos++)34           a[pos] = merge[pos];35   36   }