Sorting a list is one of the tasks computers do most: names in a register, prices in a search, election results. In 1945, when the EDVAC was still on paper, von Neumann wanted to show that the machine in his report was good for work that was not just arithmetic, and wrote by hand a program to sort and merge lists. It is one of the first programs written for a stored-program computer, and the method he used, now called merge sort, is still one of the most widely used.

Joining two sorted lists

The basic step is to merge two lists that are already in order. Just look at the first elements of each, take the smaller, and repeat:

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

Each comparison puts one number in its right place. To join two lists with $n$ elements in total, at most $n - 1$ comparisons are needed.

Divide and conquer

To sort any list, von Neumann divided it into blocks of 1 element (which are already sorted!), merged neighbours into blocks of 2, then 4, then 8, and so on:

With $n = 2^k$ elements there are $k = \log_2 n$ rounds, and each round makes at most $n$ comparisons. The total is at most

$$n \log_2 n.$$

The naive method, which looks for the smallest element, then the second smallest, and so on, makes $\frac{n(n-1)}{2}$ comparisons. For $n = 16$, that is $120$ against at most $64$. For a million names, the difference is between about 20 million comparisons and half a trillion: seconds against days.

Exercise: count the comparisons

Merge $[2, 5, 9]$ and $[3, 4, 10]$, counting the comparisons.

$2$ vs $3$: out goes $2$. $5$ vs $3$: out goes $3$. $5$ vs $4$: out goes $4$. $5$ vs $10$: out goes $5$. $9$ vs $10$: out goes $9$. The first list is used up, and $10$ goes in without a comparison. That makes $5$ comparisons for $6$ elements, within the bound of $n - 1 = 5$.

Exercise: one thousand and twenty-four elements

Compare, for $n = 1024 = 2^{10}$, the maximum number of comparisons of merge sort with that of the naive method.

Merge sort: $1024 \times 10 = 10\,240$. Naive: $\frac{1024 \times 1023}{2} = 523\,776$. Merge sort makes about $50$ times fewer comparisons, and the advantage grows with $n$.

Sources: 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).

All topics on John von Neumann · ← The von Neumann architecture: the EDVAC report · The Monte Carlo method: calculating by rolling dice →

Image credits.