Merge sort: Difference between revisions

Revision as of 09:18, 2 November 2022

Revision as of 14:54, 1 December 2022

Line 204:

result := merge(array[i], result)

'''return''' result

== Natural merge sort ==

A natural merge sort is similar to a bottom-up merge sort except that any naturally occurring [[run of a sequence|runs]] (sorted sequences) in the input are exploited. Both monotonic and bitonic (alternating up/down) runs may be exploited, with lists (or equivalently tapes or files) being convenient data structures (used as [[Queue (abstract data type)|FIFO queues]] or [[Stack (abstract data type)|LIFO stacks]]).<ref>{{cite report |last1=Powers |first1=David M. W. |last2=McMahon |first2=Graham B. |date=1983 |section=A compendium of interesting prolog programs |title=DCS Technical Report 8313 |publisher=Department of Computer Science, University of New South Wales}}</ref> In the bottom-up merge sort, the starting point assumes each run is one item long. In practice, random input data will have many short runs that just happen to be sorted. In the typical case, the natural merge sort may not need as many passes because there are fewer runs to merge. In the best case, the input is already sorted (i.e., is one run), so the natural merge sort need only make one pass through the data. In many practical cases, long natural runs are present, and for that reason natural merge sort is exploited as the key component of [[Timsort]]. Example:

Start : 3 4 2 1 7 5 8 9 0 6

Select runs : (3 4)(2)(1 7)(5 8 9)(0 6)

Merge : (2 3 4)(1 5 7 8 9)(0 6)

Merge : (1 2 3 4 5 7 8 9)(0 6)

Merge : (0 1 2 3 4 5 6 7 8 9)

Formally, the natural merge sort is said to be [[M-optimal sorting|Runs]]-optimal, where <math>\mathtt{Runs}(L)</math> is the number of runs in <math>L</math>, minus one.

[[Tournament sort|Tournament replacement selection sorts]] are used to gather the initial runs for external sorting algorithms.

==Analysis==

Line 234 ⟶ 220:

Merge sort's most common implementation does not sort in place;<ref>{{Harvtxt|Cormen|Leiserson|Rivest|Stein|2009|p=151}}</ref> therefore, the memory size of the input must be allocated for the sorted output to be stored in (see below for variations that need only ''n''/2 extra spaces).

== Natural merge sort ==

==Variants==

Variants of merge sort are primarily concerned with reducing the space complexity and the cost of copying.

A natural merge sort is similar to a bottom-up merge sort except that any naturally occurring [[run of a sequence|runs]] (sorted sequences) in the input are exploited. Both monotonic and bitonic (alternating up/down) runs may be exploited, with lists (or equivalently tapes or files) being convenient data structures (used as [[Queue (abstract data type)|FIFO queues]] or [[Stack (abstract data type)|LIFO stacks]]).<ref>{{cite report |last1=Powers |first1=David M. W. |last2=McMahon |first2=Graham B. |date=1983 |section=A compendium of interesting prolog programs |title=DCS Technical Report 8313 |publisher=Department of Computer Science, University of New South Wales}}</ref> In the bottom-up merge sort, the starting point assumes each run is one item long. In practice, random input data will have many short runs that just happen to be sorted. In the typical case, the natural merge sort may not need as many passes because there are fewer runs to merge. In the best case, the input is already sorted (i.e., is one run), so the natural merge sort need only make one pass through the data. In many practical cases, long natural runs are present, and for that reason natural merge sort is exploited as the key component of [[Timsort]]. Example:

A simple alternative for reducing 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.

Start : 3 4 2 1 7 5 8 9 0 6

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

Select runs : (3 4)(2)(1 7)(5 8 9)(0 6)

Merge : (2 3 4)(1 5 7 8 9)(0 6)

Merge : (1 2 3 4 5 7 8 9)(0 6)

Merge : (0 1 2 3 4 5 6 7 8 9)

Formally, the natural merge sort is said to be [[M-optimal sorting|Runs]]-optimal, where <math>\mathtt{Runs}(L)</math> is the number of runs in <math>L</math>, minus one.

[[Tournament sort|Tournament replacement selection sorts]] are used to gather the initial runs for external sorting algorithms.

== 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]] variants have been suggested:

* {{Harvtxt|Kronrod|1969}} suggested an alternative version of merge sort that uses constant additional space. This algorithm was later refined. {{Harv|Katajainen|Pasanen|Teuhola|1996}}

* 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 }}</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 O(n) temporary extra memory cells, by less than a factor of two. Though the algorithm is much faster in a practical way but it is unstable also 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'')²)}}.

Also,* manyMany applications of [[external sorting]] use a form of merge sorting where the input get 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 mergingmerge variant is [[block merge sort]] which creates a section of unique values to use as swap space.

* The space overhead can be reduced to sqrt(''n'') by using binary searches and rotations.<ref>{{cite web

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.

|title = A New Method for Efficient in-Place Merging

|url = https://koreascience.kr/article/CFKO200311922203087.page

|last = |date=1 Sep 2003

}}</ref> This method is employed by the C++ STL library and quadsort.<ref>{{cite web

|title = Quadsort is a branchless stable adaptive merge sort.

|url = https://github.com/scandum/quadsort

|last = |date=8 Jun 2022

}}</ref>

* 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 alternativeway forto reducingreduce 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.

==Use with tape drives==

Line 267 ⟶ 276:

[[Image:Merge sort animation2.gif|thumb|Tiled merge sort applied to an array of random integers. The horizontal axis is the array index and the vertical axis is the integer.]]

On modern computers, [[locality of reference]] can be of paramount importance in [[software optimization]], because multilevel [[Memory hierarchy|memory hierarchies]] are used. [[Cache (computing)|Cache]]-aware versions of the merge sort algorithm, whose operations have been specifically chosen to minimize the movement of pages in and out of a machine's memory cache, have been proposed. For example, the '''{{visible anchor|tiled merge sort}}''' algorithm stops partitioning subarrays when subarrays of size S are reached, where S is the number of data items fitting into a CPU's cache. Each of these subarrays is sorted with an in-place sorting algorithm such as [[insertion sort]], to discourage memory swaps, and normal merge sort is then completed in the standard recursive fashion. This algorithm has demonstrated better performance {{Examples|date=August 2016}} on machines that benefit from cache optimization. {{Harv|LaMarca|Ladner|1997}}

{{Harvtxt|Kronrod|1969}} suggested an alternative version of merge sort that uses constant additional space. This algorithm was later refined. {{Harv|Katajainen|Pasanen|Teuhola|1996}}

Also, many applications of [[external sorting]] use a form of merge sorting where the input get 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.

==Parallel merge sort==