邹永林

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

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

邹永林

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

0　引言

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

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

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

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

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

1.1算法思想

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

而国外相关著作中，一般采用“合并排序”而非“归并排序”的术语。Clifford A.Shaffer的定义［6］是：“合并排序是基于分治法的，它将一个数组分成两个长度相等的子数组，为每一个子数组排序，然后再将它们合并成一个数组”。……