主题
Search

归并排序

归并排序（或整理排序）是将两个或多个有序列表合并成一个单一有序列表（Knuth 1998, p. 158）。归并排序是最早被提出的计算机排序方法之一，并于 1945 年由约翰·冯·诺伊曼首次提出（Knuth 1998, p. 159）。变体包括双路归并排序、自然双路归并排序、直接双路归并排序和列表归并排序。

对于 a(n) 个元素的归并排序所需的最小比较次数 n，对于 n=1, 2, ... 分别是 0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, ... (OEIS A001768)。上限 b(n) 由以下序列给出

a(n)<=b(n)=1+kn-2^k
(1)

其中

k=|_log_2n_|+1,
(2)

其中 |_x_| 是向下取整函数 (Steinhaus 1999, pp. 55-56)，或者等价地，

b(n)=sum_(k=1)^n[log_2k],
(3)

给出 0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, ... (OEIS A001855)。

另请参阅

排序

使用 Wolfram|Alpha 探索

参考文献

Knuth, D. E. "Sorting by Merging." §5.2.4 in 计算机程序设计艺术，第 3 卷：排序和搜索，第 2 版。 Reading, MA: Addison-Wesley, pp. 158-168, 1998.Sloane, N. J. A. 序列 A001768/M2408 和 A001855/M2433 在 "整数序列在线百科全书" 中。Steinhaus, H. 数学快照，第 3 版。 New York: Dover, 1999.Woodall, A. D. "算法 45：使用双路归并的内部排序过程。" Comput. J. 13, 110-111, 1970.Woodrum, L. J. "使用最少比较的内部排序。" IBM Systems J. 8, 189-203, 1969.

在 Wolfram|Alpha 上被引用

归并排序

引用为

Weisstein, Eric W. "归并排序。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/MergeSort.html

主题分类