A divide-and-conquer sorting algorithm invented by John von Neumann in 1945, one of the earliest algorithms described specifically for an electronic computer, with a fuller analysis appearing in a 1948 report by Goldstine and von Neumann. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Core PrincipleSplit the input in half, recursively sort each half, then merge the two sorted halves back together in linear time, giving guaranteed O(n log n) performance regardless of the input's starting order. 1 Connections
Associated With
In Field
Source Wikipedia: Merge sort
Invented By
Source Wikipedia: Merge sort
Sources
1. Wikipedia: Merge sort
Wikimedia FoundationHistory sectionQuote, History section
invented by John von Neumann in 1945
Frequently Asked Questions
Who invented merge sort and when?
John von Neumann invented it in 1945.
John von Neumann invented merge sort in 1945, which makes it one of the earliest algorithms described specifically for an electronic computer. A fuller analysis appeared in a 1948 report by Goldstine and von Neumann. The method splits the input in half, sorts each half recursively, then merges the two sorted halves back together.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.