How did von Neumann come up with his merge sort algorithm?

Question

Since merge sort is the first $O(n \log n)$ time general purpose sorting algorithm I find it rather surprising that it was discovered without having any obvious conceptual predecessors. Are there any probable conceptual predecessors to merge sort?

Answer 1

Donald Knuth's The Art of Computer Programming (TAOCP) Vol. 3 "Sorting and Searching" gives a detailed account on the history of ideas, including the sorting by merging, in Chapter 5.5. Quoting from the 2nd Edition, pp. 383-385:

A search for the origin of today's sorting techniques takes us back to the nineteenth century, when the first machines for sorting were invented.

Towards the end of the century, the young Hermann Hollerith invented several generations of card sorting machines, for helping to accelerate the census of all U.S. American citizens.

Hollerith's card sorting machine [i.e., the later one patented in 1901 and 1904] is, of course, the basis for radix sorting methods now used in digital computers.

So radix sort can be seen as a predecessor of von Neumann's algorithm. Observe that radix sort is faster than Mergesort if the numbers to be sorted are guaranteed to be within a fixed range.

The idea of merging goes back to another card-walloping machine, the collator, which was a much later invention (1938). With its two feeding stations, it could merge two sorted decks of cards into one, in only one pass; the technique for doing this was clearly explained in the first IBM collator manual (April 1939). [See James W. Bryce, U.S. Patent 2189024 (1940).]

The chapter is definitely worth a read; Knuth lays out some more of the early developments, and for example also explains von Neumann's motivation for designing the merge sort algorithm. Von Neumann definitely did not make his algorithm out of thin air.

Hat Tip: The article by Knuth that kimchi lover mentioned in their comment is probably also worth reeading. In fact that comment made me look into TAOCP.

Answer 2

Merge sort is an algorithm based upon 'divide and conquer' with it first bring announced in 1945 by von Neumann and a detailed report three years later by himself & Goldstine. As divide and conquer is an obvious strategy - it's what Britain did to India, from all reports (and Europe to the Rest of the World) - I don't see this as being the conceptual novelty here. The naming of a concept is not as important as the substance of it - this is the matter of it and what matters.

What was new was the notion of an automaton but this had already been proposed by Charles Babbage (and even earlier by Aristotle) but without the technology precise enough to carry it out, it had to await the understanding of electromagnetic machines rather than mechanical machines. It's the actual practical novelty then, that was the key precursor that made it possible to start thinking about computers and their algorithms in a progressive manner with the results we see today.

Ref: Wikipedia