给列表排序是计算机做得最多的工作之一：登记簿里的姓名、搜索结果中的价格、选举结果。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 年关于排序的手稿被唐纳德·克努斯重新发现并加以分析，他在《计算机程序设计艺术》中描述了这份手稿。由于 EDVAC 还不存在，冯·诺依曼亲手算出程序要运行多少步，并满意地得出结论：这台机器排序会比 IBM 的穿孔卡片分类机，即当时的专用机器，更快。