[ fig sifting key through heap before proceedinglet us formally declare the variables that are evidently involved in the processvar lrxintegersrcdestfiles filerwfiles riderharray of integer(*heap* is the size of the heap we use the constant mh to denote / and are indices delimiting the heap the funnelling process can then be divided into five distinct parts read the first mh keys from src (rand put them into the upper half of the heap where no ordering among the keys is prescribed read another mh keys and put them into the lower half of the heapsifting each item into its appropriate position (build heap set to and repeat the following step for all remaining items on srcfeed to the appropriate output sequence if its key is less or equal to the key of the next item on the input sequencethen this next item belongs to the same run and can be sifted into its proper position otherwisereduce the size of the heap and place the new item into secondupper heap that is built up to contain the next run we indicate the borderline between the two heaps with the index thusthe lower (currentheap consists of the items hl- the upper (nextheap of hl hm- if then switch the output and reset to now the source is exhausted firstset to mthen flush the lower part terminating the current runand at the same time build up the upper part and gradually relocate it into positions hl hr- the last run is generated from the remaining items in the heap we are now in position to describe the five stages in detail as complete programcalling procedure switch whenever the end of run is detected and some action to alter the index of the output sequence has to be invoked in the program presented belowa dummy routine is used insteadand all runs are written onto sequence dest if we now try to integrate this program withfor instancethe polyphase sortwe encounter serious difficulty it arises from the following circumstancesthe sort program consists in its initial part of fairly complicated routine for switching between sequence variablesand relies on the availability of procedure