思路：将数组拆分，每次从中间拆分，直到不能拆分。
然后将拆分到最后的数组，再慢慢的递归回来，按顺序一个个合并
算法实现
@Test
public void sort() {
int[] arr = new int[]{8, 6, 3, 31, 2, 9, 2};
merge(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public void merge(int[] a, int start, int end) {
// 如果只剩一个元素则结束不用拆分
if(start == end) return;
// 获取拆分的中间下标
int mid = start + (end - start) / 2;
// 将左边元素加入
merge(a, start, mid);
// 将右边元素加入
merge(a, mid + 1, end);
// 拆分完毕后，开始从最后面合并数组
// 定义一个数组用于将两个需要合并的数组的值按顺序放入
int[] temp = new int[end - start + 1];
// 合并的左边数组的开始下标，一直到 ==mid为止
int i = start;
// 合并的右边数组开始下标，一直到 ==end为止
// 因为传入的 end本来就是属于数组的下标范围内
// 比如数组长度是7，传入的 start == 0， end == 6
int j = mid + 1;
// 将两个数组按顺序合并
// 使用其他方法合并也可以
for (int l = 0; l < temp.length; l++) {
// 判断两个数组有没有超出下标
// 因为 mid和 end都是数组下标范围内，所以是 <=
if(i <= mid && j <= end) {
if (a[i] < a[j]) {
temp[l] = a[i++];
} else {
temp[l] = a[j++];
}
// 超出下标则只要将另一个数组加入就好了
} else if(i == mid + 1) {
temp[l] = a[j++];
} else if(j == end + 1) {
temp[l] = a[i++];
}
}
// 将合并后的数组放回原数组
for (int k = 0; k < temp.length; k++) {
a[k + start] = temp[k];
}
}
