リストを並べ替えることは、計算機が最もよく行う仕事の一つである。名簿の名前、検索結果の価格、選挙の結果。1945 年、EDVAC がまだ紙の上にしかなかったころ、フォン・ノイマンは、報告書の機械が算術以外の仕事にも役立つことを示そうとして、リストを整列し併合するプログラムを手で書いた。これはプログラム内蔵式計算機のために書かれた最初期のプログラムの一つであり、彼が使った方法、今日マージソートと呼ばれるものは、今も最も広く使われる方法の一つである。

整列した二つのリストを併合する

基本の手順は、すでに順に並んだ二つのリストを併合することだ。それぞれの先頭の要素を見て、小さいほうを取り出し、これを繰り返せばよい。

$$[2, 5, 9] \text{ と } [3, 4, 10] \;\longrightarrow\; [2, 3, 4, 5, 9, 10].$$

比較を一回するごとに、数が一つ正しい場所に収まる。合わせて $n$ 個の要素をもつ二つのリストを併合するには、高々 $n - 1$ 回の比較で足りる。

分割統治

任意のリストを並べるために、フォン・ノイマンはそれを要素 1 個ずつのブロックに分け（これらはもう整列している！）、隣どうしを併合して 2 個のブロックに、次に 4 個、8 個と進めた。

$n = 2^k$ 個の要素があれば、$k = \log_2 n$ 回のラウンドがあり、各ラウンドの比較は高々 $n$ 回である。合計は高々

$$n \log_2 n.$$

最小の要素を探し、次に二番目に小さいものを探し、と続ける素朴な方法では、$\frac{n(n-1)}{2}$ 回の比較が必要になる。$n = 16$ なら、$120$ 回対高々 $64$ 回である。百万の名前なら、およそ二千万回の比較と五千億回の比較の差になる。数秒対数日だ。

練習：比較の回数を数える

$[2, 5, 9]$ と $[3, 4, 10]$ を併合し、比較の回数を数えよ。

$2$ 対 $3$：$2$ を取り出す。$5$ 対 $3$：$3$ を取り出す。$5$ 対 $4$：$4$ を取り出す。$5$ 対 $10$：$5$ を取り出す。$9$ 対 $10$：$9$ を取り出す。最初のリストが尽きたので、$10$ は比較なしで入る。6 個の要素に対して $5$ 回の比較で、上限 $n - 1 = 5$ の範囲内である。

練習：千二十四個の要素

$n = 1024 = 2^{10}$ について、マージソートと素朴な方法の最大比較回数を比べよ。

マージソート：$1024 \times 10 = 10\,240$。素朴な方法：$\frac{1024 \times 1023}{2} = 523\,776$。マージソートの比較はおよそ $50$ 分の 1 で済み、その差は $n$ とともに広がる。

出典： Donald E. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching（1973）· Donald E. Knuth, “Von Neumann’s first computer program”, Computing Surveys（1970）。

ジョン・フォン・ノイマンの全トピック · ← フォン・ノイマン型アーキテクチャ：EDVAC 報告書 · モンテカルロ法：サイコロを振って計算する →

画像クレジット.