从概念上讲，归并排序的工作方式如下:
类C代码的示例如下，该代码使用索引进行自顶向下归并排序算法，该算法递归地拆分列表(在这个例子中称为运行)，直到子列表大小为1，然后归并这些子列表以产生有序列表。通过将归并方向与每一级递归交替进行，可以避免写回的步骤。
// Array A[] has the items to sort; array B[] is a work array.
void TopDownMergeSort(A[], B[], n)
{
CopyArray(A, 0, n, B); // duplicate array A[] into B[]
TopDownSplitMerge(B, 0, n, A); // sort data from B[] into A[]
}
// Sort the given run of array A[] using array B[] as a source.
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
void TopDownSplitMerge(B[], iBegin, iEnd, A[])
{
if(iEnd - iBegin < 2) // if run size == 1
return; // consider it sorted
// split the run longer than 1 item into halves
iMiddle = (iEnd + iBegin) / 2; // iMiddle = mid point
// recursively sort both runs from array A[] into B[]
TopDownSplitMerge(A, iBegin, iMiddle, B); // sort the left run
TopDownSplitMerge(A, iMiddle, iEnd, B); // sort the right run
// merge the resulting runs from array B[] into A[]
TopDownMerge(B, iBegin, iMiddle, iEnd, A);
}
// Left source half is A[ iBegin:iMiddle-1].
// Right source half is A[iMiddle:iEnd-1 ].
// Result is B[ iBegin:iEnd-1 ].
void TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])
{
i = iBegin, j = iMiddle;
// While there are elements in the left or right runs...
for (k = iBegin; k < iEnd; k++) {
// If left run head exists and is <= existing right run head.
if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
B[k] = A[i];
i = i + 1;
} else {
B[k] = A[j];
j = j + 1;
}
}
}
void CopyArray(A[], iBegin, iEnd, B[])
{
for(k = iBegin; k < iEnd; k++)
B[k] = A[k];
}使用自底向上归并排序算法索引的类C代码示例如下，该算法将列表视为n个大小为1的子列表(在这个例子中称为运行步骤)，并在两个缓冲器之间来回迭代合并子列表:
// array A[] has the items to sort; array B[] is a work array
void BottomUpMergeSort(A[], B[], n)
{
// Each 1-element run in A is already "sorted".
// Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted.
for (width = 1; width < n; width = 2 * width)
{
// Array A is full of runs of length width.
for (i = 0; i < n; i = i + 2 * width)
{
// Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[]
// or copy A[i:n-1] to B[] ( if(i+width >= n) )
BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
}
// Now work array B is full of runs of length 2*width.
// Copy array B to array A for next iteration.
// A more efficient implementation would swap the roles of A and B.
CopyArray(B, A, n);
// Now array A is full of runs of length 2*width.
}
}
// Left run is A[iLeft :iRight-1].
// Right run is A[iRight:iEnd-1 ].
void BottomUpMerge(A[], iLeft, iRight, iEnd, B[])
{
i = iLeft, j = iRight;
// While there are elements in the left or right runs...
for (k = iLeft; k < iEnd; k++) {
// If left run head exists and is <= existing right run head.
if (i < iRight && (j >= iEnd || A[i] <= A[j])) {
B[k] = A[i];
i = i + 1;
} else {
B[k] = A[j];
j = j + 1;
}
}
}
void CopyArray(B[], A[], n)
{
for(i = 0; i < n; i++)
A[i] = B[i];
}对于自顶向下的归并排序算法的伪代码如下，它递归地将输入列表分成较小的子列表，直到这些子列表被简单排序，然后在返回调用链的同时归并这些子列表。
function merge_sort(list m)
// Base case. A list of zero or one elements is sorted, by definition.
if length of m ≤ 1 then
return m
// Recursive case. First, divide the list into equal-sized sublists
// consisting of the first half and second half of the list.
// This assumes lists start at index 0.
var left := empty list var right := empty list for each x with index i in m do
if i < (length of m)/2 then
add x to left else
add x to right
// Recursively sort both sublists.
left := merge_sort(left)
right := merge_sort(right)
// Then merge the now-sorted sublists. return merge(left, right)在本例中 merge 函数归并左右子列表。
function merge(left, right) var result := empty list while left is not empty and right is not empty do
if first(left) ≤ first(right) then
append first(left) to result
left := rest(left) else
append first(right) to result
right := rest(right)
// Either left or right may have elements left; consume them.
// (Only one of the following loops will actually be entered.)
while left is not empty do
append first(left) to result
left := rest(left) while right is not empty do
append first(right) to result
right := rest(right) return result对于自底向上的归并排序算法伪代码如下，它使用一个固定大小的节点引用数组，其中array[i]是对大小为2的列表的引用i 或者空。 node是指向节点的引用或指针。merge()函数类似于自顶向下合并列表示例中的merge函数，它归并两个已经排序的列表，并处理空列表。在这种情况下，merge()将使用node输入参数和返回值。
function merge_sort(node head)
// return if empty list if (head == nil) return nil var node array[32]; initially all nil var node result var node next var int i
result = head
// merge nodes into array while (result != nil)
next = result.next;
result.next = nil for(i = 0; (i < 32) && (array[i] != nil); i += 1)
result = merge(array[i], result)
array[i] = nil
// do not go past end of array if (i == 32)
i -= 1
array[i] = result
result = next
// merge array into single list
result = nil for (i = 0; i < 32; i += 1)
result = merge(array[i], result) return result自然归并排序类似于自底向上的归并排序，输入中任何自然发生的运行步骤(排序的序列)都被利用。利用列表(或等价的磁带或文件)等方便的数据结构(用作先进先出队列或者后进先出堆栈)，单调和双调(交替上/下)运行步骤都可以使用。[3]在自底向上的归并排序中，起始点假定每次运行步骤都是一个项目长。实际上，随机输入的数据中会有许多恰好有序的序列进行短期运行步骤。在典型情况下，自然归并排序可能不需要那么多遍，因为要归并的运行步骤较少。在最好的情况下，输入已经有序(即一次运行)，所以自然归并排序只需要遍历一次数据。在许多实际情况下，存在长的自然运行步骤，因此自然归并排序被用作 Timsort。如:
开始 : 3 4 2 1 7 5 8 9 0 6 选择运行 : (3 4)(2)(1 7)(5 8 9)(0 6) 归并 : (2 3 4)(1 5 7 8 9)(0 6) 归并 : (1 2 3 4 5 7 8 9)(0 6) 归并 : (0 1 2 3 4 5 6 7 8 9)
竞赛排序用于收集外部排序算法的初始运行步骤。
在排序n个对象中，归并排序拥有O(n log n)的平均性能和最坏情况下的性能。如果对长度为n的列表进行归并排序的运行时间为T(n)，那么按照算法的定义(将算法应用于原始列表一半大小的两个列表，并加上合并得到的两个列表的n步)，递推公式为T(n)=2T(n/2)+n。相近的形式源于分治算法的主定理。
在最坏的情况下，归并排序的比较次数由排序数字给出。这些数字等于或略小于(n ⌈lg n⌉2⌈lg n⌉ + 1)，介于(n lg n − n + 1)和(n lg n + n + O(lg n))之间。[4]
对于大的 n 和随机顺序的输入列表，归并排序的预期(平均)比较次数α'n 少于最坏的情况。
在最差情况下，归并排序的比较次数比快速排序在平均情况下的比较次数少39%。就移动次数而言，归并排序的最坏情况复杂度是O(n log n)—与quicksort的最佳情况下的复杂度相同，归并排序的最佳情况需要的迭代次数大约是最差情况的一半。[来源请求]
对于某些类型的列表，如果待排序的数据只能按顺序有效访问，归并排序比快速排序更有效，因此在一些语言中很流行，如Lisp，其中顺序访问的数据结构非常常见。与快速排序的一些(高效)实现不同，归并排序是一种稳定的排序。
归并排序最常见的实现并非在原列表中偏序；[5] 因此，必须为存储有序序列输出分配内存(只需n/2的额外空间的版本见下文)。
归并排序的变体主要关注降低空间复杂性和复制成本。
将空间开销减少到n/2的简单替代方案是维护左右 节点作为组合结构，仅将m的左侧部分复制到临时存储空间，引导归并 过程使其将归并输出放入m。在这个版本中，最好将临时空间分配给归并过程，因此只需要一次分配。前面提到的过度复制也得到缓解，因为回送结果 语句(函数merge 在上面的伪代码中)变得多余。
当在数组上实现时，归并排序的一个缺点是需要O(n)的运行空间。几个原地算法变体已被提出:
减少复制到多个列表的另一种方法是将新的信息字段与每个键(m中的元素被称为键)。此字段将用于在排序列表中将键和任何相关信息链接在一起(键及其相关信息称为记录)。然后，通过改变链接值来进行排序列表的归并；根本不需要移动任何记录。仅包含一个链接的字段通常会小于整个记录，因此也将使用更少的空间。这是一种标准排序技术，不限于归并排序。
当要排序的数据太大而无法容纳时，在光盘或者磁带驱动器上进行外部归并排序非常实用。 外部排序解释如何用磁盘驱动器实现归并排序。典型的磁带机类型使用四个磁带机。所有的输入/输出都是顺序的(除了每一遍结束时的倒带)。一个最小的实现只需要两个记录缓冲区和几个程序变量就可以完成。
将四个磁带机命名为A、B、C、D，原始数据在A上，并且只使用两个记录缓冲区，算法类似于 ，使用成对的磁带机而非内存中的阵列。基本算法可以描述如下:
通常情况下，外部排序使用混合算法而不是从非常短的运行步骤开始，初始过程将把许多记录读入内存，进行内部排序以创建一个长运行步骤，然后将这些长运行步骤分配到输出集。这一步避免了许多遍早期归并。例如，一个1024条记录的内部排序将保存9个归并过程。内部排序通常很大，因为它这样的好处。事实上，有些技术可以使初始运行步骤的长度大小高于可用内存。[10]
有了更高级的算法，上述算法可以修改为使用三个磁带。使用两个队列，或一个栈和一个队列，或三个栈也可以达到O（n log n)的运行时间。另一方面，使用k（k>2）个磁带(内存中有O(k)个项)，利用k/2路归并，我们可以将磁带操作数量减少到O(log k)次。
优化磁带(和磁盘)驱动器使用的更复杂的归并排序是多相归并排序。
在现代计算机上， 参考点在 软件优化方面至关重要，因为使用了多级内存层次结构。利用高速缓存的归并排序算法已被提出，该算法明确选择最小化存储器高速缓存中页面调入调出的移动次数。例如，平铺归并排序算法在子阵列达到大小为S时停止划分子阵列，其中S是适合于中央处理器高速缓存的数据项的数量。这些子阵列中的每一个都用原地排序算法进行排序，例如插入排序，以避免内存交换，然后以标准递归方式完成普通的归并排序。该算法在受益于缓存优化的机器上表现出了更好的性能[示例请求]。 （）
提出了归并排序的替代版本，该版本使用恒定的额外空间。这个算法后来被改进了。（）
此外，许多外部排序的应用使用归并排序的形式，其中输入被分割成更多数量的子列表，理想情况下，这是数量满足归并后仍能使当前处理的页的集合适配主存储器。
由于使用了分治法，归并排序并行性很好。 科曼、莱瑟森、瑞文斯特和斯坦的第三版算法导论讨论了几个平行的变体。[11] 其中的第一个可以很容易地用伪代码表达分支合并关键词:
// Sort elements lo through hi (exclusive) of array A.algorithm mergesort(A, lo, hi) is
if lo+1 < hi then // Two or more elements.
mid = ⌊(lo + hi) / 2⌋ fork mergesort(A, lo, mid)
mergesort(A, mid, hi) join
merge(A, lo, mid, hi)这个算法是对串行版本的一个微不足道的修改，它的加速并不令人印象深刻:当在无限数量的处理器上执行时，它运行的时间复杂度为Θ(n)，这只是一个Θ(log n) 串行版本的改进。使用并行归并算法可以获得更好的结果，这给出了并行下 Θ(n / (log n)2)的时间复杂度，这意味着如果有足够的处理器可用的时间，这种类型的并行归并排序运行的复杂度为
。[11] 当与快速稳定的顺序排序相结合时，这种排序在实践中可以表现良好，例如插入排序和快速顺序归并作为归并小阵列的基本情况。[12]
归并排序是最早实现的最佳速度的排序算法之一，理查德·科尔使用巧妙的二次采样算法来确保O(1)归并。[13] 其他复杂度的并行排序算法可以在较低的常数时间内实现相同或更好的时间界限。例如，在1991年，大卫·鲍尔斯描述了一个并行化的快速排序(和一个相关的基数排序)可以在具有n个处理器的CRCW并行随机存取机（PRAM）上通过隐式执行分区在O(log n)时间复杂度内运行。[14]鲍尔斯[15]还展示了一个在蝴蝶排序网络上时间复杂度为O((log n)2)的Batcher的双调归并排序算法，比起在PRAM上运行的O(log n)复杂度，它实际上更快，他详细讨论了比较、基数和并行排序中隐藏的开销。
尽管堆排序与归并排序有相同的时间限制，它只需要θ(1)的辅助空间而非归并排序的θ(n)。在典型的现代架构上，高效的快速排序在对基于内存的数组进行排序时，实现通常优于归并排序。另一方面，归并排序是一种稳定的排序，在处理访问缓慢的顺序介质时效率更高。归并排序通常是排序链表的最佳方式：在这种情况下，以只需要θ(1)额外空间的方式实现归并排序相对容易，并且链表的缓慢随机访问性能使得一些其他算法(例如快速排序)性能较差，而另一些算法(例如堆排序)完全不可能。
截至 Perl 5.8，归并排序是它的默认排序算法(它在早期版本的Perl中是快速排序)。在Java中，Arrays.sort() 方法根据数据类型使用归并排序或优化的快速排序，并且为了高效实现，当排序的数组元素少于7个时切换为插入排序。[16] Linux内核对其链表使用归并排序。[17] Python使用Timsort，这是归并排序和插入排序的另一种优化混合，已成为 Java SE 7（对于非基元类型的数组）[18]， 安卓平台[19] 和 GNU Octave[20]中的标准排序算法。
^Knuth（1998， p. 158）.
^Katajainen, Jyrki; Träff, Jesper Larsson (March 1997). "A meticulous analysis of mergesort programs" (PDF). Proceedings of the 3rd Italian Conference on Algorithms and Complexity. Italian Conference on Algorithms and Complexity. Rome. pp. 217–228. CiteSeerX 10.1.1.86.3154. doi:10.1007/3-540-62592-5_74..
^Powers, David M. W. and McMahon Graham B. (1983), "A compendium of interesting prolog programs", DCS Technical Report 8313, Department of Computer Science, University of New South Wales..
^The worst case number given here does not agree with that given in Knuth's Art of Computer Programming, Vol 3. The discrepancy is due to Knuth analyzing a variant implementation of merge sort that is slightly sub-optimal.
^Cormen; Leiserson; Rivest; Stein. Introduction to Algorithms. p. 151. ISBN 978-0-262-03384-8..
^Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Practical in-place mergesort". Nordic J. Computing. 3 (1): 27–40. CiteSeerX 10.1.1.22.8523..
^Geffert, Viliam; Katajainen, Jyrki; Pasanen, Tomi (2000). "Asymptotically efficient in-place merging". Theoretical Computer Science. 237: 159–181. doi:10.1016/S0304-3975(98)00162-5..
^Huang, Bing-Chao; Langston, Michael A. (March 1988). "Practical In-Place Merging". Communications of the ACM. 31 (3): 348–352. doi:10.1145/42392.42403..
^Kim, Pok-Son; Kutzner, Arne (2004). Stable Minimum Storage Merging by Symmetric Comparisons. European Symp. Algorithms. Lecture Notes in Computer Science. 3221. pp. 714–723. CiteSeerX 10.1.1.102.4612. doi:10.1007/978-3-540-30140-0_63. ISBN 978-3-540-23025-0..
^Selection sort. Knuth's snowplow. Natural merge..
^Cormen 等人 2009，第797–805页.
^Victor J. Duvanenko "Parallel Merge Sort" Dr. Dobb's Journal & blog[1] and GitHub repo C++ implementation [2].
^Cole, Richard (August 1988). "Parallel merge sort". SIAM J. Comput. 17 (4): 770–785. CiteSeerX 10.1.1.464.7118. doi:10.1137/0217049.
^Powers, David M. W. Parallelized Quicksort and Radixsort with Optimal Speedup, Proceedings of International Conference on Parallel Computing Technologies. Novosibirsk. 1991..
^David M. W. Powers, Parallel Unification: Practical Complexity, Australasian Computer Architecture Workshop, Flinders University, January 1995.
^OpenJDK src/java.base/share/classes/java/util/Arrays.java @ 53904:9c3fe09f69bc.
^linux kernel /lib/list_sort.c.
^jjb. "Commit 6804124: Replace "modified mergesort" in java.util.Arrays.sort with timsort". Java Development Kit 7 Hg repo. Archived from the original on 2018-01-26. Retrieved 24 Feb 2011..
^"Class: java.util.TimSort<T>". Android JDK Documentation. Archived from the original on January 20, 2015. Retrieved 19 Jan 2015..
^"liboctave/util/oct-sort.cc". Mercurial repository of Octave source code. Lines 23-25 of the initial comment block. Retrieved 18 Feb 2013. Code stolen in large part from Python's, listobject.c, which itself had no license header. However, thanks to Tim Peters for the parts of the code I ripped-off..
暂无