1945-合併排序#

案件摘要#

1945 年，約翰·馮·諾伊曼（John von Neumann）為尚未建成的 EDVAC 電腦親手寫下一段合併排序（merge sort）程式。這是「存儲程序式電腦」概念問世後，第一批為這種新機器設計的演算法之一。案件的核心疑問是：當程式與資料一樣被存進記憶體、由機器逐步執行指令時，排序應該長什麼樣子？馮·諾伊曼的手稿給出了答案——把問題切半、各自解決、再線性合併，這個分治策略日後成為演算法設計最重要的範式。

前因 -- 為什麼會有這個案子#

ENIAC（1945）沒有存儲程序：改一次程式要重新接線好幾天，排序這種工作在當時主要靠 IBM 卡片分類機（card sorter），以打孔卡片逐位分發，本質上是指數式的基數排序，一次只能處理一個欄位。
1945 年 6 月，馮·諾伊曼寫下《First Draft of a Report on the EDVAC》，提出「程式與資料同存於記憶體」的存儲程序架構，機器讀取指令即可執行。
新架構需要示範「程序存儲在記憶體中」到底能做到什麼，於是馮·諾伊曼為 EDVAC 撰寫合併排序程式（1945 年手稿），做為這類機器的第一批演算法示範。
當時既有的插入排序（insertion sort）對 n 筆資料需要 O(n²) 次比較，資料量一大就不可行；工程界也面臨磁帶等外部儲存媒體上大量資料排序的實際需求。

線索與推理 -- 數學式、程式、理論#

線索一：分治法與主定理#

合併排序把陣列切成兩半，遞迴排序後再合併。若合併需要 O(n) 時間，遞迴式為：

\[ T(n) = 2T(n/2) + O(n) \]

由主定理（Master Theorem）， \(a=2\) 、 \(b=2\) 、 \(f(n)=O(n)\) ，因為 \(n^{\log_b a} = n\) ，落在第二種情況，得：

\[ T(n) = O(n \log n) \]

線索二：合併步驟的線性結構#

兩個已排序序列合併時，每次只需比較兩序列的首元素，取較小者，因此合併長度 m 與 k 的兩序列至多 \(m+k-1\) 次比較——這是整個演算法效率的關鍵：

def merge(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    return out + a[i:] + b[j:]

線索三：決策樹下界——為什麼 O(n log n) 已是極限#

任何只靠「比較」的排序演算法，其行為可畫成一棵決策樹：每個內部節點是一次比較的兩種結果，每片葉子對應一種排列。n 筆資料有 n! 種排列，樹必須有至少 n! 片葉子，二元樹高度至少為：

\[ \log_2(n!) = \Theta(n \log n) \]

（由 Stirling 近似 \(n! \approx \sqrt{2\pi n}\,(n/e)^n\) 。）因此合併排序的 \(O(n \log n)\) 已貼近比較排序的下界 Ω(n log n)。

線索四：穩定性與對照#

合併時用 <= 取左邊元素，相等元素維持原相對順序，因此合併排序是穩定排序。
插入排序最壞需要 \(n(n-1)/2\) 次比較，為 \(O(n^2)\) ；對 n = 100 萬筆資料， \(n^2\) 與 \(n \log n\) 相差約 5 萬倍。

破案時刻：可執行驗證#

import random, math

comparisons = 0

def merge_sort(a):
    global comparisons
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        comparisons += 1
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

for n in [1000, 10000, 100000]:
    comparisons = 0
    data = [random.random() for _ in range(n)]
    result = merge_sort(data)
    assert result == sorted(data)
    ratio = comparisons / (n * math.log2(n))
    print(f"n={n:6d}  比較次數={comparisons:9d}  次數/(n log n)={ratio:.2f}")

執行結果顯示，隨機資料下比較次數約為 \(n \log_2 n\) 的 0.8 至 1.0 倍，實證了 \(O(n \log n)\) 的理論分析。

結案 -- 後果與影響#

分治法（divide and conquer）自此成為演算法設計的核心範式，日後的快速排序、傅立葉變換（FFT）、Strassen 矩陣乘法都循此思路。
合併的線性合併思想延伸為外部排序：磁帶時代的資料排序靠多路合併（multiway merge）處理遠超記憶體的資料量。
Timsort（Python 與 Java 的標準排序）本質是合併排序的適應性變體，結合插入排序處理小段，並利用真實資料的既有有序段。
決策樹下界 Ω(n log n) 成為排序理論的基石，也是「證明演算法下界」的第一個經典範例。
這份手稿也標誌著演算法正式成為一門與硬體分離、可獨立分析的學問。

關鍵人物與文獻#

John von Neumann, First Draft of a Report on the EDVAC, Moore School of Electrical Engineering, University of Pennsylvania, 1945.
John von Neumann, 合併排序手稿（1945），收錄於 John von Neumann: Selected Letters（American Mathematical Society / London Mathematical Society, 2005）。
Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998（第 5.2.4 節詳述合併排序史與 von Neumann 手稿）。
Jon L. Bentley, M. Douglas McIlroy, "Engineering a Sort Function", Software: Practice and Experience, 23(11), 1993.
Tim Peters, Timsort, Python Software Foundation, 2002（CPython listsort 說明文件）。