- Person
- John von Neumann
- Lived
- 1903–1957
- Field
- Mathematics & computing
- From
- Hungarian-American
The story
Sorting, putting a list of items in order, is one of the most common tasks a computer performs. Doing it efficiently matters enormously when the list holds millions of records, and how a machine would handle sorting was one of the questions John von Neumann considered when estimating how much memory a computer would need.
In 1945, while thinking about how the planned EDVAC computer would be used, John von Neumann devised a method now called merge sort. The idea is elegant: split the list in half, sort each half, then merge the two sorted halves into one by repeatedly taking the smaller of the two front items. Applied over and over, the method sorts any list in a number of steps that grows only modestly as the list gets longer.
He wrote out by hand a program for the merging step, a 23-page manuscript that his colleague Herman Goldstine kept among his papers. In 1970 the computer scientist Donald Knuth published a study of it titled Von Neumann's First Computer Program, examining the insights it contained, suggesting improvements and pointing out a bug. A detailed description and analysis of a bottom-up version of merge sort appeared in a report by Goldstine and von Neumann in 1948.
Merge sort has several useful properties. It is stable, meaning that items with equal keys keep their original order, and it works well on data that can only be read in sequence, which made it ideal for tapes and linked lists. It can also be split across many processors.
Merge sort remains a staple of computer science courses and of real software. It has been Perl's default sorting method since version 5.8, Java uses it for sorting objects, and the Linux kernel uses it for linked lists. Timsort, a hybrid of merge sort and insertion sort, is used by Python and by the Java and Android platforms.
Why it matters
Merge sort helps computers everywhere organise data quickly, from databases to search results.
About John von Neumann
Budapest-born mathematician whose 1945 EDVAC report set out the stored-program design behind almost every computer, and who helped found game theory and modern quantum mechanics.
More about John von Neumann
- Von Neumann warned of CO2 warming in 1955In 1955 John von Neumann noted that carbon dioxide from burning coal and oil might already have changed the atmosphere enough to cause general warming.
- Von Neumann's ergodic theorem earned 'immortality'John von Neumann's 1932 papers on ergodic theory were so important that Paul Halmos said they alone would have guaranteed him mathematical immortality.
- Von Neumann launched computer weather forecastingIn 1950 John von Neumann and Jule Charney used ENIAC to make the first numerical weather forecasts; in 1955 routine computer forecasting began in the US.
- John von Neumann founded game theoryJohn von Neumann proved the minimax theorem in 1928 and, with Oskar Morgenstern, published Theory of Games and Economic Behavior in 1944, founding game theory.
- Von Neumann's IAS computer was copied worldwideThe IAS machine John von Neumann built in Princeton from 1946 became the blueprint for early computers worldwide, and its design shaped IBM's first scientific computers.
- Von Neumann helped create the Monte Carlo methodWith Stanislaw Ulam, John von Neumann helped develop the Monte Carlo method, using random numbers on computers to solve problems too complex for direct calculation.
- Von Neumann gave quantum mechanics its mathematicsIn his 1932 book Mathematical Foundations of Quantum Mechanics, John von Neumann set out the first rigorous mathematical framework for quantum theory.
- Von Neumann designed a machine that copies itselfIn the late 1940s John von Neumann designed a self-reproducing 'universal constructor' and, with Stanislaw Ulam, created the field of cellular automata.
- John von Neumann wrote the blueprint for modern computersJohn von Neumann's 1945 report on the EDVAC gave the first published description of the stored-program computer, the design behind almost every computer since.
Sources
- John von Neumann Wikipedia
- Merge sort Wikipedia
Another act of tikkun olam. This is part of tikkun olam, the Jewish idea of repairing the world, and every one of us can add to it.