if then : else : endfor : to - do runs set( [ ] [ ]end naturallystatement ( is to decrement whenever an input source ceases hencepredicate ( may easily be expressed by the relation statement ( )howeveris more difficult to refineit consists of the repeated selection of the least key among the available sources and its subsequent transport to the destinationi the current output sequence the process is further complicated by the necessity of determining the end of each run the end of run may be reached because (athe subsequent key is less than the current key or (bthe end of the source is reached in the latter case the source is eliminated by decrementing in the former case the run is closed by excluding the sequence from further selection of itemsbut only until the creation of the current output run is completed this makes it obvious that second variablesay is needed to denote the number of sources actually available for the selection of the next item this value is initially set equal to and is decremented whenever run teminates because of condition (aunfortunatelythe introduction of is not sufficient we need to know not only the number of filesbut also which files are still in actual use an obvious solution is to use an array with boolean components indicating the availability of the files we choosehowevera different method that leads to more efficient selection procedure whichafter allis the most frequently repeated part of the entire algorithm instead of using boolean arraya file index mapsay is introduced this map is used so that - are the indices of the available sequences thus statement ( can be formulated as followsk : repeat select the minimal keylet [mbe the sequence number on which it occursruns copy( [ [ ]] [ ])if [ [ ]eof then eliminate sequence elsif [ [ ]eor then close run end until since the number of sequences will be fairly small for any practical purposethe selection algorithm to be specified in further detail in the next refinement step may as well be straightforward linear search the statement eliminate sequence implies decrease of as well as and also reassignment of indices in the map the statement close run merely decrements and rearranges components of accordingly the details are shown in the following procedurebeing the last refinement the statement switch files is elaborated according to explanations given earlier procedure balancedmerge (srcfiles file)files file(adens _mergesorts *var ijmtxintegerlk integerminxintegertarray of integer(*index map*rruns rider(*source*fgarray of files filerwarray of runs riderbegin runs set(rsrc)for : to - do [ :files new("")files set( [ ] [ ] end(*distribute initial runs from src to [ [ - ]* : : repeat