table example of natural mergesort as an exampletable shows the file in its original state (line and after each pass (lines - in natural merge sort involving numbers note that only three passes are needed the sort terminates as soon as the number of runs on is (we assume that there exists at least one non-empty run on the initial sequencewe therefore let variable be used for counting the number of runs merged onto by making use of the type rider defined in sect the program can be formulated as followsvar lintegerr files rider(*see *repeat files set( )files set( )files set( )distribute( )(* to and *files set( )files set( )files set( ) : merge( (* and into *until the two phases clearly emerge as two distinct statements they are now to be refinedi expressed in more detail the refined descriptions of distribute (from rider to riders and and merge (from riders and to rider followrepeat copyrun( )if ~ eof then copyrun( end until eof repeat mergerun( )inc(luntil eofif ~ eof then copyrun( )inc(lend this method of distribution supposedly results in either equal numbers of runs in both and bor in sequence containing one run more than since corresponding pairs of runs are mergeda leftover run may still be on file awhich simply has to be copied the statements merge and distribute are formulated in terms of refined statement mergerun and subordinate procedure copyrun with obvious tasks when attempting to do soone runs into serious difficultyin order to determine the end of runtwo consecutive keys must be compared howeverfiles are such that only single element is immediately accessible we evidently cannot avoid to look aheadi to associate buffer with every sequence the buffer is to contain the first element of the file still to be read and constitutes something like window sliding over the file instead of programming this mechanism explicitly into our programwe prefer to define yet another level of abstraction it is represented by new module runs it can be regarded as an extension of module files of sect introducing new type riderwhich we may consider as an extension of type files rider this new type will not only accept all operations available on riders and indicate the end of filebut also indicate the end of run and the first element of the remaining part of the file the new type as well as its