归并排序

思路：将数组拆分，每次从中间拆分，直到不能拆分。
然后将拆分到最后的数组，再慢慢的递归回来，按顺序一个个合并

算法实现

@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];
        }
    }