the merge sort algorithm apparently compares well with even the advanced sorting techniques discussed in the previous howeverthe administrative overhead for the manipulation of indices is relatively highand the decisive disadvantage is the need for storage of items this is the reason sorting by merging is rarely used on arraysi on data located in main store figures comparing the real time behavior of this mergesort algorithm appear in the last line of table they compare favorably with heapsort but unfavorably with quicksort natural merging in straight merging no advantage is gained when the data are initially already partially sorted the length of all merged subsequences in the -th pass is less than or equal to kindependent of whether longer subsequences are already ordered and could as well be merged in factany two ordered subsequences of lengths and might be merged directly into single sequence of + items mergesort that at any time merges the two longest possible subsequences is called natural merge sort an ordered subsequence is often called string howeversince the word string is even more frequently used to describe sequences of characterswe will follow knuth in our terminology and use the word run instead of string when referring to ordered subsequences we call subsequence ai aj such that (ai- ai(aki aj+ maximal run orfor shorta run natural merge sortthereforemerges (maximalruns instead of sequences of fixedpredetermined length runs have the property that if two sequences of runs are mergeda single sequence of exactly runs emerges thereforethe total number of runs is halved in each passand the number of required moves of items is in the worst case *log( )but in the average case it is even less the expected number of comparisonshoweveris much larger because in addition to the comparisons necessary for the selection of itemsfurther comparisons are needed between consecutive items of each file in order to determine the end of each run our next programming exercise develops natural merge algorithm in the same stepwise fashion that was used to explain the straight merging algorithm it employs the sequence structure (represented by filessee sect instead of the arrayand it represents an unbalancedtwo-phasethree-tape merge sort we assume that the file variable represents the initial sequence of items (naturallyin actual data processing applicationthe initial data are first copied from the original source to for reasons of safety and are two auxiliary file variables each pass consists of distribution phase that distributes runs equally from to and band merge phase that merges runs from and to this process is illustrated in fig merge phase distribution phase st run nd run nth run fig sort phases and passes