becomes necessary to retain the keys of the last item of the last run on each sequence fortunatelyour implementation of runs does exactly this in the case of output sequencesr first represents the item last written next attempt to describe the distribution algorithm could therefore be repeat selectif [jfirst < first then continue old run endcopyrun until eof the obvious mistake here lies in forgetting that [jfirst the obvious mistake here lies in forgetting that - destination sequences without inspection of first the remaining runs are distributed as followswhile ~ eof do selectif [jfirst < first then copyrunif eof then inc( [ ]else copyrun end else copyrun end end now we are finally in position to tackle the main polyphase merge sort algorithm its principal structure is similar to the main part of the -way merge programan outer loop whose body merges runs until the sources are exhaustedan inner loop whose body merges single run from each sourceand an innermost loop whose body selects the initial key and transmits the involved item to the target file the principal differences to balanced merging are the following instead of nthere is only one output sequence in each pass instead of switching input and output sequences after each passthe sequences are rotated this is achieved by using sequence index map the number of input sequences varies from run to runat the start of each runit is determined from the counts di of dummy runs if di for all ithen - dummy runs are pseudo-merged into single dummy run by merely incrementing the count dn- of the output sequence otherwiseone run is merged from all sources with di and di is decremented for all other sequencesindicating that one dummy run was taken off we denote the number of input sequences involved in merge by it is impossible to derive termination of phase by the end-of status of the - 'st sequencebecause more merges might be necessary involving dummy runs from that source insteadthe theoretically necessary number of runs is determined from the coefficients ai the coefficients ai were computed during the distribution phasethey can now be recomputed backward the main part of the polyphase sort can now be formulated according to these rulesassuming that all - sequences with initial runs are set to be readand that the tape map is initially set to repeat (*merge from [ [ - to [ - ]* : [ - ] [ - : repeat (*merge one run* : (*determine no of active sequences*for : to - do if [ then dec( [ ]