归并排序的概念与算法设计

邹永林

（常熟理工学院计算机学院，常熟　215500）

归并排序的概念与算法设计

邹永林

（常熟理工学院计算机学院，常熟215500）

0　引言

归并排序是一种重要的内部排序方法，在数据结构课程中作为一类独特的排序方法专门进行介绍和讨论。但是，其算法设计在教学实践中常与合并排序混为一谈，这在一定程度上造成了对归并排序概念的曲解和算法设计的缺失。

本文首先分析了归并排序与合并排序的差异，进而对标准的归并排序算法设计进行了探讨。

1　归并排序与合并排序的差异

关于利用归并思想进行排序的方法，英文著作中采用“Merge Sort”一词标识，中文文献中有两个术语：“归并排序”和“合并排序”，在数据结构课程中常采用前者，在算法分析课程中采用后者，但在进行算法设计与分析时，使用相同的算法代码进行说明。

实际上，归并排序和合并排序之间，存在着一定的差异。以下分别从算法思想和排序过程两个方面进行讨论。

1.1算法思想

在国内绝大多数数据结构著作［1-5］中，一般使用“归并排序”一词，且采用严蔚敏等的定义，即：“假设初始序列含有n个记录，则可看成是n个有序子序列，每个子序列的长度为1，然后两两归并，得到「n/2⌉个长度为2或1的有序子序列；再两两归并，…，如此重复，直到得到一个长度为n的有序序列为止”。

而国外相关著作中，一般采用“合并排序”而非“归并排序”的术语。Clifford A.Shaffer的定义［6］是：“合并排序是基于分治法的，它将一个数组分成两个长度相等的子数组，为每一个子数组排序，然后再将它们合并成一个数组”。Anany Levitin的定义［7］是，“对于一个需要排序的数组A［0…n-1］，合并排序把它一分为二：A［0…⌊n/2」-1］和A［n/⌊2…n」-1］，并对每个子数组递归排序，然后把这两个排好序的子数组合并为一个有序数组”。

从上述定义中可以看出，归并排序和合并排序是两个不同的概念，合并排序强调分治思想，利用一分为二的方法将一个待排序序列分成基本相等的两个子序列，递归进行排序；而归并排序更注重两两归并，至于如何将一个长度为n的待排序序列分解成n个长度为1的有序子序列，没有具体约定。

1.2排序过程

在排序过程中，根据待排序序列的长度不同，归并排序和合并排序也有差别。

当序列长度n取2的幂次方时，归并排序和合并排序的过程完全一致。因为此时待排序序列总能划分为两个相等且长度为2的幂次方的子序列。

但更一般的情况是，当n取非2的幂次方时，排序过程完全不同［2-5］。假设以一个含有11个元素的待排序序列｛49，38，65，97，76，13，27，49，85，36，21｝为例，排序过程分别如图1和图2所示。

图1是按照合并排序思想进行排序的完整过程。可以看出，每次分区时，均以当前待排序区间的长度的一半⌊ni/2」进行子区间划分，直至得到n个长度为1的子序列，然后进行两两合并完成排序；而在图2中，从第四次划分的结果开始，描述了符合归并排序定义的过程，体现了（相邻元素）两两归并的特点，并不关心如何从一个包含n个元素的待排序序列得到n个长度为1的子序列。

根据上述分析，可以得到以下结论：合并排序和归并排序是两个不同的概念，其共同点是排序过程都借助2-路归并的方法进行，其差别体现在如何从一个长度为n的序列得到n个长度为1的子序列。因此，可以认为，合并排序和归并排序是归并类排序的两种不同方法，合并排序算法不能准确描述归并排序的所有可能情况。换句话说，归并排序的算法不能以合并排序算法完全代替。

图1　合并排序的过程示意图

2　归并排序的算法设计

参照合并排序的算法，可以设计出符合标准归并排序思想的算法。

在图2中，合并前的分区过程描述了归并排序借鉴合并排序的分区方法进行递归分区并得到符合归并排序思想的n个长度为1的子序列的具体过程。从这个递归分区过程可以看出，当对一个长度为n的待排序序列进行归并排序时，只要将每次分区的长度设置为2的幂次方即可。

对应的归并排序的算法代码可设计如下：

图2　归并排序的过程示意图

与标准的合并排序算法相比，上述算法中专门设置了一个参数del，作为分区的基准长度，实现按照2的幂次方值的递减序列进行递归分区的目的。参数del的取值可根据实际长度n计算得到，在主函数中提前确定。

对图2中的实例利用上述算法进行排序，可得到与图2完全一致的结果。

另外，从图1和图2描述的排序过程可知，对于一个包含n个元素的序列，归并排序与合并排序的效率完全相同。

3　讨论

本文通过对合并排序和归并排序的概念和排序过程的分析，明确了两者之间的联系和区别，据此提出了归并类排序的概念，并将两者归属其下；然后，借鉴合并排序的算法，完成了归并排序算法的设计，并通过实例验证了算法的正确性。

本文的研究有助于规范和完善数据结构课程中有关归并排序的知识体系和教学内容，也可为学习和理解归并排序知识提供帮助。

［1］严蔚敏，吴伟民.数据结构（C语言版）［M］.清华大学出版社，2014：283-284.

［2］胡学钢.数据结构（C语言版）［M］.高等教育出版社，2004：168-169.

［3］吴仁群.数据结构简明教程［M］.机械工业出版社，2011：193-195.

［4］周桂红.数据结构［M］.北京邮电大学出版社，2010：218-221.

［5］张晓莉，王苗，罗文劼.数据结构与算法［M］.机械工业出版社，2008：245-247.

［6］Clifford A.Shaffer.数据结构与算法分析［M］.电子工业出版社，1998：164-166.

［7］Anany Levitin.算法设计与分析基础［M］.清华大学出版社，2007：95-97.

Order by Merging；Sequencing by Merging；Partition；Algorithm Design

Concept and Algorithm Design of Merge Sort

ZOU Yong-lin
（School of Computer Science and Engineering，Changshu Institute of Technology，Changshu 215500）

1007-1423（2015）20-0048-04

10.3969/j.issn.1007-1423.2015.20.011

邹永林（1963-），男，江苏常熟人，硕士，副教授，研究方向为算法分析与设计

2015-04-21

2015-07-01

从算法思想和排序过程两方面讨论归并排序和合并排序的区别，指出归并排序算法不能以合并排序算法完全替代；进而借鉴合并排序算法设计符合标准的归并排序思想的算法，并通过实例验证算法的正确性。

归并排序；合并排序；分区；算法设计

Discusses the differences between merge sort（order by merging）and merge sort（sequencing by merging）on two aspects of algorithm thought and sorting process，points out that the algorithm of merge sort（order by merging）cannot be entirely replaced by merge sort（sequencing by merging）；designs the algorithm of merge sort（order by merging）referencing the standard merge sort algorithm，takes an example to verify the correctness of the algorithm.