リストを並べ替えることは、計算機が最もよく行う仕事の一つである。名簿の名前、検索結果の価格、選挙の結果。1945 年、EDVAC がまだ紙の上にしかなかったころ、フォン・ノイマンは、報告書の機械が算術以外の仕事にも役立つことを示そうとして、リストを整列し併合するプログラムを手で書いた。これはプログラム内蔵式計算機のために書かれた最初期のプログラムの一つであり、彼が使った方法、今日マージソートと呼ばれるものは、今も最も広く使われる方法の一つである。 整列した二つのリストを併合する 基本の手順は、すでに順に並んだ二つのリストを併合することだ。それぞれの先頭の要素を見て、小さいほうを取り出し、これを繰り返せばよい。 $$[2, 5, 9] \text{ と } [3, 4, 10] \;\longrightarrow\; [2, 3, 4, 5, 9, 10].$$比較を一回するごとに、数が一つ正しい場所に収まる。合わせて $n$ 個の要素をもつ二つのリストを併合するには、高々 $n - 1$ 回の比較で足りる。 分割統治 任意のリストを並べるために、フォン・ノイマンはそれを要素 1 個ずつのブロックに分け（これらはもう整列している！）、隣どうしを併合して 2 個のブロックに、次に 4 個、8 個と進めた。 この対話型の図を使うには JavaScript を有効にしてください。議論の全体は本文にあります。 $n = 2^k$ 個の要素があれば、$k = \log_2 n$ 回のラウンドがあり、各ラウンドの比較は高々 $n$ 回である。合計は高々 $$n \log_2 n.$$最小の要素を探し、次に二番目に小さいものを探し、と続ける素朴な方法では、$\frac{n(n-1)}{2}$ 回の比較が必要になる。$n = 16$ なら、$120$ 回対高々 $64$ 回である。百万の名前なら、およそ二千万回の比較と五千億回の比較の差になる。数秒対数日だ。 方眼紙の上のプログラム 整列についてのフォン・ノイマンの 1945 年の手稿は、ドナルド・クヌースによって再発見・分析され、『The Art of Computer Programming』で紹介されている。EDVAC はまだ存在しなかったので、フォン・ノイマンはプログラムが何ステップかかるかを手で計算し、この機械は当時の専用機械である IBM のパンチカード分類機よりも速く整列できる、と満足げに結論した。 練習：比較の回数を数える$[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$ の範囲内である。