本题用的是递归的方法，为了更了解递归，可以看一下下面这篇文章：
关于递归中return的理解（最浅显易懂）_Mr Liu的博客-CSDN博客_递归函数return怎么理解
=========================================================================
在讲解归并排序之前，先介绍一个概念：
位移操作符（位运算符）：
- >> 右移
- << 左移
举个例子：
- 12 >> 1: 12的二进制表示是00001100，将00001100二进制数向右移一位，变为00000110，转化为十进制就是6
- 15 >> 1: 15的二进制表示是00001111，将00001111这个二进制数向右移一位，变为00000111，也就是7
通过上面的例子，不难发现x >> 1，相当于x除以2，若有余数，则向下取整。
注：加(减)所用时间<乘(除)所用时间
位运算所用时间<乘(除)所用时间（一般情况下）
=========================================================================
归并排序是一个典型的基于分治的递归算法。分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。
分治法，字面意思是“分而治之”，就是把一个复杂的问题分成多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并。即，分治法的思想是将原问题拆解成相同或者相似的子问题，直到子问题可以简单的直接求解。
归并排序的整体思路： 合并两个有序数组的过程： 动图演示： 分解说明：Java 代码实现：
private static void mergeSort(int[] arr) {
if (arr.length == 0) return;
//result是递归过程中的临时数组
int[] result = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, result);
}
//对 arr 的【start， end】区间进行归并排序
private static void mergeSort(int[] arr, int start, int end, int[] result) {
//递归出口：只有一个数字时，停止拆分
if (start == end) return;
int middle = (start + end) >> 1;
//拆分左边区域，并将归并排序结果存放在result数组中
mergeSort(arr, start, middle, result);
//拆分右边区域，并将归并排序结果存放在result数组中
mergeSort(arr, middle + 1, end, result);
//合并左右区域到result的【start， end】区间
merge(arr, start, end, result);
}
private static void merge(int[] arr, int start, int end, int[] result) {
int middle = (start + end) >> 1;
//用来遍历的指针
int p1 = start; int p2 = middle + 1;
//result数组的下边
int resultIndex = start;
while (p1 <= middle && p2 <= end) {
// if (arr[p1] > arr[p2]) {
// result[resultIndex] = arr[p2];
// p2++;
// resultIndex++;
// } else {
// result[resultIndex] = arr[p1];
// p1++;
// resultIndex++;
// }
result[resultIndex++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
}
//此时的情况：左区域有数字，右区域没有数字，则将左区域剩余的数字补到result数组之后
while (p1 <= middle) {
result[resultIndex++] = arr[p1++];
}
//此时的情况：左区域没有数字，右区域有数字，则将右区域剩余的数字补到result数组之后
while (p2 <= end) {
result[resultIndex++] = arr[p2++];
}
//将result操作区间的数字拷贝到arr数组中，以便下次比较
for (int i = start; i <= end; i++) {
arr[i] = result[i];
}
}
=========================================================================
这道题让我想起来一道属于easy级别的算法题: LeetCode88题：合并两个有序数组
合并两个有序数组（Java）——LeetCode88_Shliry的博客-CSDN博客
