Merge sort
Ordenamiento por mezcla (merge sort)
- Date
- 1945-1948 · confidence high
- Place
- Princeton, New Jersey, United States
- Credited to
- John von Neumann
- Field
- Knowledge & symbols
What it is
John von Neumann devised in 1945 the merge sort algorithm, which splits a list into progressively smaller parts, sorts them separately and merges them back together, achieving O(n log n) performance far better than simpler sorting methods.
Von Neumann programmed a version for the EDVAC in 1945; a detailed description and its analysis appeared in a report by Goldstine and von Neumann in 1948.
What it led to
- the 'divide and conquer' algorithm paradigm
- one of the first algorithms formally analyzed for digital computers
- the basis of stable sorting implementations used today in programming languages