Editing Merge sort (section)

== In-place merge sort==

One drawback of merge sort, when implemented on arrays, is its {{math|''O''(''n'')}} working memory requirement. Several methods to reduce memory or make merge sort fully [[In-place algorithm|in-place]] have been suggested:

* {{Harvtxt|Kronrod|1969}} suggested an alternative version of merge sort that uses constant additional space.
* Katajainen ''et al.'' present an algorithm that requires a constant amount of working memory: enough storage space to hold one element of the input array, and additional space to hold {{math|''O''(1)}} pointers into the input array. They achieve an {{math|''O''(''n'' log ''n'')}} time bound with small constants, but their algorithm is not stable.<ref>{{harvtxt|Katajainen|Pasanen|Teuhola|1996}}</ref>
* Several attempts have been made at producing an ''in-place merge'' algorithm that can be combined with a standard (top-down or bottom-up) merge sort to produce an in-place merge sort. In this case, the notion of "in-place" can be relaxed to mean "taking logarithmic stack space", because standard merge sort requires that amount of space for its own stack usage. It was shown by Geffert ''et al.'' that in-place, stable merging is possible in {{math|''O''(''n'' log ''n'')}} time using a constant amount of scratch space, but their algorithm is complicated and has high constant factors: merging arrays of length {{mvar|n}} and {{mvar|m}} can take {{math|5''n'' + 12''m'' + ''o''(''m'')}} moves.<ref>{{Cite journal | doi = 10.1016/S0304-3975(98)00162-5| title = Asymptotically efficient in-place merging| journal = Theoretical Computer Science| volume = 237| pages = 159–181| year = 2000| last1 = Geffert | first1 = Viliam| last2 = Katajainen | first2 = Jyrki| last3 = Pasanen | first3 = Tomi| issue = 1–2| doi-access = free}}</ref> This high constant factor and complicated in-place algorithm was made simpler and easier to understand. Bing-Chao Huang and Michael A. Langston<ref name="Research Contributions">{{cite journal |first1=Bing-Chao |last1=Huang |first2=Michael A. |last2=Langston |title=Practical In-Place Merging |date=March 1988 |journal=Communications of the ACM |volume=31 |issue=3 |pages=348–352 |doi=10.1145/42392.42403|s2cid=4841909 |doi-access=free }}</ref> presented a straightforward linear time algorithm ''practical in-place merge'' to merge a sorted list using fixed amount of additional space. They both have used the work of Kronrod and others. It merges in linear time and constant extra space. The algorithm takes little more average time than standard merge sort algorithms, free to exploit {{Math|''O''(''n'')}} temporary extra memory cells, by less than a factor of two. Though the algorithm is much faster in a practical way, it is unstable for some lists. But using similar concepts, they have been able to solve this problem. Other in-place algorithms include SymMerge, which takes {{math|''O''((''n'' + ''m'') log (''n'' + ''m''))}} time in total and is stable.<ref>{{Cite conference| doi = 10.1007/978-3-540-30140-0_63| chapter = Stable Minimum Storage Merging by Symmetric Comparisons| conference = European Symp. Algorithms| volume = 3221| pages = 714–723| series = Lecture Notes in Computer Science| year = 2004| last1 = Kim | first1 = Pok-Son| last2 = Kutzner | first2 = Arne| title = Algorithms – ESA 2004| isbn = 978-3-540-23025-0| citeseerx=10.1.1.102.4612}}</ref> Plugging such an algorithm into merge sort increases its complexity to the non-[[linearithmic]], but still [[quasilinear time|quasilinear]], {{math|''O''(''n'' (log ''n'')<sup>2</sup>)}}.
* Many applications of [[external sorting]] use a form of merge sorting where the input gets split up to a higher number of sublists, ideally to a number for which merging them still makes the currently processed set of [[page (computer memory)|pages]] fit into main memory.
* A modern stable, linear, and in-place merge variant is [[block merge sort]], which creates a section of unique values to use as swap space.
* The space overhead can be reduced to {{Math|''O''(&radic;''n'')}} by using binary searches and rotations.<ref>{{cite journal
 |title       = A New Method for Efficient in-Place Merging
 |url         = https://koreascience.kr/article/CFKO200311922203087.page
 |journal = Proceedings of the Korean Institute of Intelligent Systems Conference
 |date=1 Sep 2003
|pages = 392–394
 |last1 = Kim
 |first1 = Pok-Son
 |last2 = Kutzner
 |first2 = Arne
 }}</ref> This method is employed by the C++ STL library and quadsort.<ref name="quadsort"/>
* An alternative to reduce the copying into multiple lists is to associate a new field of information with each key (the elements in ''m'' are called keys). This field will be used to link the keys and any associated information together in a sorted list (a key and its related information is called a record). Then the merging of the sorted lists proceeds by changing the link values; no records need to be moved at all. A field which contains only a link will generally be smaller than an entire record so less space will also be used. This is a standard sorting technique, not restricted to merge sort.
* A simple way to reduce the space overhead to ''n''/2 is to maintain ''left'' and ''right'' as a combined structure, copy only the ''left'' part of ''m'' into temporary space, and to direct the ''merge'' routine to place the merged output into ''m''. With this version it is better to allocate the temporary space outside the ''merge'' routine, so that only one allocation is needed. The excessive copying mentioned previously is also mitigated, since the last pair of lines before the ''return result'' statement (function '' merge ''in the pseudo code above) become superfluous.