sorting sequences straight merging unfortunatelythe sorting algorithms presented in the preceding are inapplicableif the amount of data to be sorted does not fit into computer' main storebut if it isfor instancerepresented on peripheral and sequential storage device such as tape or disk in this case we describe the data as (sequentialfile whose characteristic is that at each moment one and only one component is directly accessible this is severe restriction compared to the possibilities offered by the array structureand therefore different sorting techniques have to be used the most important one is sorting by merging merging (or collatingmeans combining two (or moreordered sequences into singleordered sequence by repeated selection among the currently accessible components merging is much simpler operation than sortingand it is used as an auxiliary operation in the more complex process of sequential sorting one way of sorting on the basis of mergingcalled straight mergingis the following split the sequence into two halvescalled and merge and by combining single items into ordered pairs call the merged sequence aand repeat steps and this time merging ordered pairs into ordered quadruples repeat the previous stepsmerging quadruples into octetsand continue doing thiseach time doubling the lengths of the merged subsequencesuntil the entire sequence is ordered as an exampleconsider the sequence in step the split results in the sequences the merging of single components (which are ordered sequences of length )into ordered pairs yields splitting again in the middle and merging ordered pairs yields third split and merge operation finally produces the desired result each operation that treats the entire set of data once is called phaseand the smallest subprocess that by repetition constitutes the sort process is called pass or stage in the above example the sort took three passeseach pass consisting of splitting phase and merging phase in order to perform the sortthree tapes are neededthe process is therefore called three-tape merge actuallythe splitting phases do not contribute to the sort since they do in no way permute the itemsin sense they are unproductivealthough they constitute half of all copying operations they can be eliminated altogether by combining the split and the merge phase instead of merging into single sequencethe output of the merge process is immediately redistributed onto two tapeswhich constitute the sources of the subsequent pass in contrast to the previous two-phase merge sortthis method is called single-phase merge or balanced merge it is evidently superior because only half as many copying operations are necessarythe price for this advantage is fourth tape we shall develop merge program in detail and initially let the data be represented as an array which