例子

==

下面通过一个例子来看看归并排序是怎么工作的，原数组如下。

第一步：分解

首先将数组分解成两部分，即19、15、37为一组，12、25为一组，为了区分，我们起个名字叫“第一层”，如下图：

第二步：分解

继续分解，19、15为一组，37为一组，12为一组，25为一组，这四组为“第二层”，如下图：

第三步：分解

继续分解，此时只剩下19、15这一组可以分解，分解成19、15，这两组为“第三层”，如下图：

第四步：归并

由于所有组都已经分解成只有1个元素，开始进行归并，从“高层”开始归并，即先归并“第三层”，比较“第三层”两组元素，19 < 15，因此将15排在19前面，由于已经没有元素，结束此次归并，如下图：

第五步：归并

继续归并，此次归并“第二层”，这一层有4个组，进行两两比较。首先，比较15、19和37：15 < 37，所以15放第一个位置，接着比较19和37，19 < 37，所以19放第二个位置，此时第一组15、19已经没有元素，于是将37填入15和19之后。接着比较：12和25：12 < 25，所以12放第一个位置，由于第一组12已经没有元素，于是将25填入12之后。归并的结果如下：

第六步：归并

继续归并，此次归并“第一层”，这一组有2个组，第一组：15、19、37，第二组：12、25。同样的，取两组的第1个数比较：15 > 12，所以12放第1个位置；接着取第二组的第2个数比较：15 < 25，所以15放第2个位置；接着取第一组的第2个数比较：19 < 25，所以19放第3个位置；接着取第一组的第3个数比较：37 > 25，所以25放第4个位置；由于第二组已经没有元素，所以37自然归入第5个位置。此时，归并结束，最终数组如下。

整个例子的完整过程图如下：

完整过程

====

用一张动图来展示整个归并排序的过程。图中，开始每个柱子的颜色都不同，代表所有数字被分解成了各自一组，红色的柱子代表归并后的数列。

整合

==

合并的代码在开头已经给过了，分解的代码 《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》无偿开源 威信搜索公众号【编程进阶路】 较简单，就是递归调用归并方法，最后调用合并方法，最终代码如下。

public class MergeSort {

public static void mergeSort(int[] array) {

if (array == null || array.length == 0)

return;

int[] temp = new int[array.length];

mergeSort(array, 0, array.length - 1, temp);

}

// 归并

private static void mergeSort(int array[], int first, int last, int temp[]) {

if (first < last) {

int mid = (first + last) / 2;

mergeSort(array, first, mid, temp); // 递归归并左边元素

mergeSort(array, mid + 1, last, temp); // 递归归并右边元素

mergeArray(array, first, mid, last, temp); // 再将二个有序数列合并

}

}

/**

• 合并两个有序数列

• array[first]~array[mid]为第一组

• array[mid+1]~array[last]为第二组

• temp[]为存放两组比较结果的临时数组

*/

private static void mergeArray(int array[], int first, int mid, int last, int temp[]) {

int i = first, j = mid + 1; // i为第一组的起点, j为第二组的起点

int m = mid, n = last; // m为第一组的终点, n为第二组的终点

int k = 0; // k用于指向temp数组当前放到哪个位置

while (i <= m && j <= n) { // 将两个有序序列循环比较, 填入数组temp

if (array[i] <= array[j])

temp[k++] = array[i++];

else

temp[k++] = array[j++];

}

while (i <= m) { // 如果比较完毕, 第一组还有数剩下, 则全部填入temp

temp[k++] = array[i++];

}

while (j <= n) {// 如果比较完毕, 第二组还有数剩下, 则全部填入temp

temp[k++] = array[j++];

}

for (i = 0; i < k; i++) {// 将排好序的数填回到array数组的对应位置

array[first + i] = temp[i];

}

}

}

时间复杂度