概念介绍
有同学想了解归并排序，今天它来了！归并排序的基本思想是“分治”，也是就把一个大问题递归分成许多个小问题依次求解。咱们直接上例子。
图片来源（https://www.cnblogs.com/chengxiao/p/6194356.html）
咱们对{ 8, 4, 5, 7, 1, 3, 6, 2 }进行排序，对于分的过程，咱们只是把一个待排序的整体数组，分成了一个个小的单元，此时数组的顺序并未发生任何改变。分完了之后，就是治，治的过程是将各个小单元合并成有序序列，如下图，8与4，5与7，1与3，6和2都进行了排序，形成一个个有序序列。
那么小单元是如何合并的？咱们举个例子：对[4,8]和[5,7]进行排序。我们要知道，A=[4,8]和B=[5,7]本身就是有序序列，由上图可以看到合并的结果，但是看不到合并的过程。两个数组是这样比的：先取A[0] = 4，B[0] = 5进行比较，4<5，将4从A中移除，放入到一个新的数组C中，此时A=[8]，B=[5,7]，C=[4]。然后重复上述操作，取A[0] = 8，B[0] = 5进行比较,8>5,将5从B中移除，放入C中，此时此时A=[8]，B=[7]，C=[4，5],最后就是8和7比较了。总结就是：每次取两个有序数组的头结点进行比较，小的结点放入新的数组中。
代码实现
// 分+治的过程 public static void mergeSort(int[] arr, int left, int right, int[] temp) { if (left < right) { // 通过mid将代分的数组分成两部分 int mid = (left + right) / 2; // 从左向mid递归 mergeSort(arr, left, mid, temp); // 从mid向右递归 mergeSort(arr, mid + 1, right, temp); // 合并 merge(arr, left, mid, right, temp); } } /** * 合并过程 * * @param arr 排序的原始数组 * @param left 左边有序序列的初始索引 * @param mid 中间索引 * @param right 右边索引 * @param temp 做中转的数组 */ public static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left; // 初始化i，左边有序序列的初始索引 int j = mid + 1; // 初始化j，右边有序序列的初始索引 int t = 0; // 指向temp数组的当前索引 // （一）先把左右两边（有序）的数组按照规则填充到temp数组，直到左右两边的有序序列，有一边处理完毕为止 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[t] = arr[i]; i++; t++; } else { temp[t] = arr[j]; j++; t++; } } // （二）把剩余数据的一边数据依次全部填充到temp中 while (i <= mid) { temp[t] = arr[i]; i++; t++; } while (j <= right) { temp[t] = arr[j]; j++; t++; } // （三）将temp数组的元素拷贝到arr t = 0; int tempLeft = left; while (tempLeft <= right) { arr[tempLeft] = temp[t]; t++; tempLeft++; } }
至此，代码编写完成，Git地址：https://github.com/HollowCup/algorithms-and-data-structure，具体实现位于algorithm工程下的sort目录MergeSort，如果发现不足之处，请联系我进行更改，十分感谢！关注我，带你了解更多排序算法！