合并排序(Merge Sort)算法是非常通用的排序算法,是稳定排序,即便在最差的情况下也还有 O(nlogn) 的时间复杂度。

合并排序法(Merge Sort)

合并排序法的概念

合并排序法是最典型的分治(Divide and Conquer)算法,将一整个串行分割成一个个元素,再两两一组依照元素大小填入至新的空间中来合并成新的,并且已经排序好的串行。

合并排序法的过程

假设现在有个数组数据,内容如下:

索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79

要如何将它递增排列呢?

首先将数组对半切成:

索引    0   1   2   3   4   |   5   6   7   8   9
数值   69  81  30  38   9   |   2  47  61  32  79

再对半切成:

索引    0   1   |   2   3   4   ||   5   6   |   7   8   9
数值   69  81   |  30  38   9   ||   2  47   |  61  32  79

再对半切成:

索引    0   |   1   ||   2   |   3   4   |||   5   |   6   ||   7   |   8   9
数值   69   |  81   ||  30   |  38   9   |||   2   |  47   ||  61   |  32  79

再对半切成:

索引    0   ||   1   |||   2   ||   3   |   4   ||||   5   ||   6   |||   7   ||   8   |   9
数值   69   ||  81   |||  30   ||  38   |   9   ||||   2   ||  47   |||  61   ||  32   |  79

已经不能再切了,即可开始合并,一边合并一边把元素照顺序排好:

索引    0    |   1    ||   2    |   3       4    |||   5   |    6    ||   7    |   8       9
数值   69    |  81    ||  30    |   9      38    |||   2   |   47    ||  61    |  32      79
                                   →───←                                     →───←

继续合并:

索引    0        1     |   2        3       4     ||   5       6     |   7        8       9
数值   69       81     |   9       30      38     ||   2      47     |  32       61      79
       →────←       →────────←        →───←        →────────←

继续合并:

索引    0        1         2        3       4      |   5       6         7        8       9
数值    9       30        38       69      81      |   2      32        47       61      79
       →─────────────────←         →─────────────────←

继续合并:

索引    0        1         2        3       4          5       6         7        8       9
数值    2        9        30       32      38         47      61        69       79      81
       →────────────────────────────────────────←

合并完成,也排序完成了!

合并排序法的排序过程动画

以上过程看起来十分直觉。程序实作时需要使用额外的空间来进行一边合并一边排序的动作。

合并排序法的程序实作

在实作程序的时候,应该要避免使用递归(Recursive)的结构,因为递归需要不断地重新建构函数的堆栈空间,硬件资源的负担会比较大,且若是递归层数过多还会导致堆栈溢出(Stack Overflow)。所以比较好的做法还是在一个函数内以循环迭代的方式来完成。

为了化简递归转迭代结构时的问题,在这里不采取从中间开始分割的方式,而是直接跳过分割的动作,从合并开始进行。在观察合并排序法的分割过程后,其实不难发现完整的子数组的长度,合并过后的长度都会再乘上 2,且即便是未达 2 的乘幂长度的数组,也能进行合并的动作。也就是说,分割的动作其实并非必要,可以直接从前端开始直接合并 2 的乘幂个元素,先从 1 (20)个元素两两开始合并,再从 2 (21)个元素两两开始合并,再从 4 (22)个元素两两开始合并,再从 8 (23)个元素两两开始合并,依此类推。因此可以写出如下的迭代版合并排序法:

<< 1 等同于「乘 2」。

合并排序法的复杂度

以 #{{n}}# 来表示要排序的数据笔数。

项目 值 备注
最差时间复杂度 #{{O(n \log n)}}#
最佳时间复杂度 #{{O(n \log n)}}#
平均时间复杂度 #{{O(n \log n)}}#
最差空间复杂度 #{{O(n)}}#
是否稳定 是