主題
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)。

另請參閱

排序

使用 探索

參考文獻

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.

在 上被引用

歸併排序

引用為

Weisstein, Eric W. "歸併排序。" 來自 Web 資源。 https://mathworld.tw/MergeSort.html

主題分類