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?
2 Answers
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.
-
1$\begingroup$ Specifically, the line that says “The existence of efficient special-purpose sorting machines provided a natural standard by which the merits of his proposed computer organization could be evaluated.” — so von Neumann wrote a merge sort program to match the special-purpose merge-sorting machine (collator). $\endgroup$ Jan 11, 2021 at 19:02
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
-
$\begingroup$ It's unclear if Von Neumann called the thechnique "divide and conquer" (or was motivated by that phrase) but even if he did transfering that rhetorical device into a mathematical theorem seems highly nontrivial to say the least $\endgroup$– GEPNov 30, 2020 at 14:17
-
3$\begingroup$ A glance at Knuth's 1970 "Von Neumann's first computer program", Computing Surveys, Vol. 2, No. 4, December 1970, makes it unlikely that Von Neumann used the term "divide and conquer" in his 1945 note. $\endgroup$ Nov 30, 2020 at 16:00
-
3$\begingroup$ This answer doesn't cite any historical sources or mention von Neumann, who is specifically asked about in the title of the question. This would have been better as a comment. $\endgroup$– user466Nov 30, 2020 at 20:31
-
1$\begingroup$ @Ben Crowell: The term 'divide and conquer' was used in the wikipedia article I quoted from ... $\endgroup$ Dec 2, 2020 at 17:52