Class | Sorting algorithm |
---|---|
Data structure | Array |
Worst-case performance | |
Best-case performance | typical, natural variant |
Average performance | |
Worst-case space complexity | total with auxiliary, auxiliary with linked lists[1] |
In computer science, merge sort (also commonly spelled as mergesort and as merge-sort[2]) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the relative order of equal elements is the same in the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945.[3] A detailed description and analysis of bottom-up merge sort appeared in a report by Goldstine and von Neumann as early as 1948.[4]