计算机科学考古：冯·诺依曼的第一个计算机程序
The following article is from dingtingli Author dingtingli
你知道谁是归并排序的发明者吗？它是在何时、伴随着怎样的历史背景诞生的？
多数人可能只有一个模糊的概念，普遍认为这是冯·诺依曼的成就。然而，关于这一发明的具体细节，甚至连维基百科都未能提供全面的解答。
冯·诺依曼设计归并排序的初衷，是作为一项对编程语言和计算机架构的重要测试，因此它也是最早期的计算机程序之一。
本文的目的就是揭开归并排序背后的历史面纱。为了深入理解这一算法的起源，我们将共同回溯早期计算机架构的发展脉络。
归并排序的手稿
归并排序的历史问题，同样也吸引了《计算机程序设计艺术》的作者高德纳的注意。
论文：冯·诺依曼的第一个计算机程序
论文地址：
计算机架构的早期发展
要理解冯·诺依曼的第一个程序，首先要了解其背后的时代背景。
20 世纪 30 至 40 年代，电子计算器开始被使用，人们迫切需要高速计算器。例如，差分分析器等模拟机器当时被广泛使用。
在这个背景下，工程师 Eckert 提出了一项关于电子机器（electrical machine）的计划。这个提议获得了美国政府的支持，这也催生了 ENIAC 计算机的诞生。
在 ENIAC 的基础上，EDVAC 机器进行了诸多改进，其中之一就是将并行电路系统转变为串行系统。冯·诺依曼也作为该项目的顾问加入了进来。
EDVAC 采用了冯·诺依曼架构，这种设计与现代计算机架构类似。它包含了串行计算设计、多个寄存器以及辅助内存。这种创新为后续的计算机技术发展奠定了重要基础。
在这种系统中，存在修改和引用内存的指令。尽管这不是完美的设计，但它标志着计算机架构和编程领域的重要开端。
归并排序的原始程序
我们现在来探讨一下冯·诺伊曼的程序，这份用墨水手写的手稿共有 23 页。
在第一页上，我们还能依稀看到之前用铅笔写下的“绝密”字样，不过这些字迹后来被人擦掉了。要知道，在 1945 年，计算机研究由于涉及到军事问题，都被列为机密。
当时 IBM 一款机器 IBM Collators，其功能是将两叠已排序好的卡片合并成一叠。
冯·诺伊曼选择排序作为主题，目的是为了比较计算机排序“所需时间”与 IBM 的专用排序机器的时间。
在手稿的开头，冯·诺伊曼首先明确了排序记录的概念：即如何将两个已分别排序的记录串合并为一个有序的单一序列。
接着，他说明了这个程序的目标：
“我们想要制定出排序和合并（网状化）的代码指令，并且要弄清楚这些指令需要占用多少控制容量以及它们的执行时间。”
基于当时 IBM 专用排序机器的工作方式，手稿中制定了以下合并方法：
假设我们有两个列表 x 和 y，每个列表包含已排序的记录。n' 和 m' 分别是当前正在考虑合并的 x 和 y 列表中的记录的位置指针。
手稿中根据合并过程的状态分为四种情况：
情况 (a) 两个列表都有剩余记录 (`n' < n, m' < m)：这种情况有两个子情况： (a1) key(x_n') ≤ key(y_m')：如果 x 的当前记录小于等于 y 的当前记录：选取 x 的这条记录，然后 x 的位置指标 n' 增加 1。 (a2) key(x_n') > key(y_m')：如果 x 的当前记录大于 y 的当前记录：选取 y 的这条记录，然后 y 的位置指标 m' 增加 1。
情况 (b) 只有 x 列表有剩余记录 (n' < n, m' = m)：操作与子情况 (a1) 相同，继续选取 x 的记录，n' 增加 1。
情况 (c) 只有 y 列表有剩余记录 (n' = n, m' < m)：操作与子情况 (a2) 相同，继续选取 y 的记录，m' 增加 1。
情况 (d) 两个列表都没有剩余记录 (n' = n, m' = m)：这标志着合并过程的完成。
在这份手稿中并没有真正完成整个排序程序的编码，只描述了合并过程。
就像大多数程序一样，这个手稿也有一个小错误。如果冯·诺伊曼有机会在一台 EDVAC 上运行这个程序，他肯定会体验到调试的过程。
总结
冯·诺伊曼并不是在尝试编写一个最优的排序程序，他只是在试验性地探索一种指令代码，作为一项对编程语言和计算机架构的重要测试。
但这份手稿不仅仅是一个草率的草图，它显然是经过一定的仔细思考而成的。对这份手稿的细致分析，更像是一个窗口，让我们洞察编程中挑战性的概念是如何生成的。
时间的流逝并没有减弱归并排序的重要性，一代代的计算机科学家一直在不断地优化着它。这个算法在今天仍然在许多复合的排序算法中扮演着关键角色，比如 TimSort 算法。
冯·诺依曼可能从未想象到，他的这一创造对数据排序产生的影响。至今，仍然有无数的计算机设备运行着他手稿中的合并过程。
参考资料：
https://compileralchemy.substack.com/p/merge-sort-and-its-early-history http://public.callutheran.edu/~reinhart/CSC521MSCS/Week5/KnuthVonNeumann.pdf