1 public static void mergeSort(int[] arr) {
2 if (arr == null || arr.length < 2) {
3 return;
4 }
5 mergeSort(arr, 0, arr.length - 1);
6 }
7
8 public static void mergeSort(int[] arr, int l, int r) {
9 if (l == r) {
10 return;
11 }
12 int mid = l + ((r - l) >> 1);
13 mergeSort(arr, l, mid); //左侧有序
14 mergeSort(arr, mid + 1, r); //右侧有序
15 merge(arr, l, mid, r); //merge
16 }
17
18 public static void merge(int[] arr, int l, int m, int r) {
19 int[] help = new int[r - l + 1];
20 int i = 0;
21 int p1 = l;
22 int p2 = m + 1;
23 while (p1 <= m && p2 <= r) {
24 help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; //谁小拷贝谁（p1和p2都不越界）
25 }
26 while (p1 <= m) {
27 help[i++] = arr[p1++];
28 }
29 while (p2 <= r) {
30 help[i++] = arr[p2++];
31 }
32 for (i = 0; i < help.length; i++) {
33 arr[l + i] = help[i];
34 }
35
如果看代码的流程，归并排序的是把一组数据，一分为二，之后对左边的数据继续一分为二，分到实在不能再分（也就是l == r的时候）
最后再排序！这其实是分而治之的思想，假设有5个数【2,4,9,6,3】我们直接排序不好排，但是如果我们分一下呢？
变成【2,4】和【9,6,3】如果对左边再分一次呢？
【2】、【4】这时候2 和 4 都是单独的一个数，我们显然知道单独的一个数是最好排序的，2 和4 本身就是有序的，因为它们只有自己！
对于左边，当分到不能再分的时候return;，递归调用的“递”的过程就完成了，接下来就是归了。
在归的过程中，会多次进入右侧的递归函数，但是由于 l == r 所以实质上右侧的调用是无效的，只需要调用merge函数完成左侧单个数据
的依次排序！
当左侧完成的时候，会进入最初始的那个 l 和 r 的值，接下来再次进入右侧的递归函数，完成同样的一个过程，最后左侧数据和右侧数据
都是各自有序的，当程序跳出（mergeSort(arr, mid + 1, r); //右侧有序）这一行代码的时候，会执行最外层函数的最后一次merge，这时候
对所有数据完成最后一次排序参数应该是最初的参数，也就是 l = 0 ; mid = 2 ; r = 4 ！ merge（0,2.4） 这时候所有数据就都是有序的了！
代码的执行顺序？
当进入一条递归语句的时候，会多次循环整个过程，只有当满足结束条件的时候，才会return！
但此时要注意，这时候return只是退出了这一条语句而已，对于最外层的函数来说，只是这一条
语句执行完毕了。还是需要继续往下执行的，也就是会进入下一条递归语句，对于归并排序来说
先进入左边递归，左边有序，之后进入右边递归，右边有序！最后进入最外层的函数执行最后一
条merge语句，把整个数组完成排序！
下面是我画的一个草图：
