给列表排序是计算机做得最多的工作之一：登记簿里的姓名、搜索结果中的价格、选举结果。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$ 倍，而且 $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 报告 · 蒙特卡洛方法：掷骰子来计算 →

图片来源.