图片素材与文字描述来自：尚硅谷-韩顺平数据结构与算法。
1、基本思想
归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各个结果有序的合并在一起，即分而治之)。
2、算法描述
(1) 分阶段可以理解为就是递归拆分子序列的过程，如下图(图来自韩顺平数据结果与算法课程)：
(2) 治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤（图来自韩顺平数据结果与算法课程）：
3、代码实现
public class MergerSort { public static void main(String[] args) { Long startTime = System.currentTimeMillis(); //int[] array = new int[]{10, 1, 9, 2, 8, 3, 7, 4, 6, 5}; int[] array = new int[100000]; for (int i = 0; i < 100000; i++) { array[i] = (int) (Math.random() * 100000); } mergerSort(array, 0, array.length - 1); Long endTime = System.currentTimeMillis(); System.out.println((endTime - startTime) + " " + array.length); } public static void mergerSort(int[] array, int low, int high) { if (low < high) { // 中间索引 int mid = (low + high) / 2; // 左递归分解 mergerSort(array, low, mid); // 右递归分解 mergerSort(array, mid + 1, high); // 有序合并 merger(array, low, mid, high); } } private static void merger(int array[], int low, int mid, int high) { int[] temp = new int[high - low + 1]; // 左侧有序序列起始索引 int i = low; // 右侧有序序列起始索引 int j = mid + 1; // 临时数组起始索引 int k = 0; // 左右两侧的有序序列按照顺序填充至temp数组 while (i <= mid && j <= high) { if (array[i] <= array[j]) { temp[k++] = array[i++]; } else { temp[k++] = array[j++]; } } // 左侧数组还剩余元素入temp while (i <= mid) { temp[k++] = array[i++]; } // 右侧数组还剩余元素入temp while (j <= high) { temp[k++] = array[j++]; } // 将temp数组复制到array for (int x = 0; x < temp.length; x++) { array[x + low] = temp[x]; } // System.out.println(Arrays.toString(array)); } }
原文：https://www.cnblogs.com/Latiny/p/11082097.html
