归并排序可以总结成3步：
1、确定中间分界点mid
2、递归处理左边界，递归处理右边界
3、合并两个边界
和快速排序不同的是，归并排序是先递归左右区间再合并，归并的难点就在于合并的过程
代码模板如下：
public class MergeSort {
public int[] sortArray(int[] nums) {mergeSort(nums, 0, nums.length-1);
return nums;
}
public void mergeSort(int[] nums, int left, int right) {if (left >= right) return;
int mid = (left + right) /2;
int i=left, j=mid+1,k=0;
//递归左边界
mergeSort(nums, i, mid);
//递归右边界
mergeSort(nums, mid+1, right);
int[] temp = new int[right-left+1];
//合并两个边界数据
while (i<= mid && j<= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
}else {
temp[k++] =nums[j++];
}
}//比较后左区间还有值
while (i<= mid) {
temp[k++] = nums[i++];
}//比较后右区间还有值
while (j<= right) {
temp[k++] = nums[j++];
}//把临时数组数据写回原数组
for (i=left,j=0;i<=right;i++,j++) {
nums[i] = temp[j];
}
}
}
