Editing Merge sort (section)

== 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.