Editing Merge sort (section)

{{Short description|Divide and conquer sorting algorithm}}
{{Infobox Algorithm
|name={{PAGENAMEBASE}}|class=[[Sorting algorithm]]
|image=Merge-sort-example-300px.gif
|caption=An example of merge sort. First, divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally, all the elements are sorted and merged.
|data=[[Array data structure|Array]]
|time=<math>O(n\log n)</math>
|best-time=<math>\Omega(n\log n)</math> typical,
<math>\Omega(n)</math> natural variant
|average-time=<math>\Theta(n\log n)</math>
|space=<math>O(n)</math> total with <math>O(n)</math> auxiliary, <math>O(1)</math> auxiliary with linked lists<ref>{{Harvtxt|Skiena|2008|p=122}}</ref>
}}

In [[computer science]], '''merge sort''' (also commonly spelled as '''mergesort''' and as {{nowrap|'''merge-sort'''}}<ref name="goodrich12">{{cite book |title=Data structures and algorithms in Python |chapter=Chapter 12 - Sorting and Selection |last1=Goodrich |first1=Michael T. |last2=Tamassia |first2=Roberto |last3=Goldwasser |first3=Michael H. |date=2013 |edition=1st |location=Hoboken [NJ] |publisher=Wiley |isbn=978-1-118-29027-9 |pages=538–549 }}</ref>) is an efficient, general-purpose, and [[comparison sort|comparison-based]] [[sorting algorithm]]. Most implementations of merge sort are [[Sorting algorithm#Stability|stable]], which means that the relative order of equal elements is the same between the input and output. Merge sort is a [[divide-and-conquer algorithm]] that was invented by [[John von Neumann]] in 1945.<ref>{{Harvtxt|Knuth|1998|p=158}}</ref> A detailed description and analysis of bottom-up merge sort appeared in a report by [[Herman Goldstine|Goldstine]] and von Neumann as early as 1948.<ref>{{cite conference |chapter=A meticulous analysis of mergesort programs |date=March 1997 |first1=Jyrki |last1=Katajainen |first2=Jesper Larsson |last2=Träff |title=Algorithms and Complexity |series=Lecture Notes in Computer Science |volume=1203 |conference=Italian Conference on Algorithms and Complexity |location=Rome |book-title=Proceedings of the 3rd Italian Conference on Algorithms and Complexity |pages=217–228 |doi=10.1007/3-540-62592-5_74 |isbn=978-3-540-62592-6 |citeseerx=10.1.1.86.3154 |chapter-url=http://hjemmesider.diku.dk/~jyrki/Paper/CIAC97.pdf}}</ref>