end until enddec(zuntil runs set( [ [ - ]] [ [ - ]])(*rotate sequences*tn : [ - ]dn : [ - ] : [ - ]for : - to by - do [ : [ - ] [ : [ - ] [ : [ - endt[ :tnd[ :dna[ :zdec(leveluntil level return [ [ ]end polyphase distribution of initial runs we were led to the sophisticated sequential sorting programsbecause the simpler methods operating on arrays rely on the availability of random access store sufficiently large to hold the entire set of data to be sorted often such store is unavailableinsteadsufficiently large sequential storage devices such as tapes or disks must be used we know that the sequential sorting methods developed so far need practically no primary store whatsoeverexcept for the file buffers andof coursethe program itself howeverit is fact that even small computers include random accessprimary store that is almost always larger than what is needed by the programs developed here failing to make optimal use of it cannot be justified the solution lies in combining array and sequence sorting techniques in particularan adapted array sort may be used in the distribution phase of initial runs with the effect that these runs do already have length of approximately the size of the available primary data store it is plain that in the subsequent merge passes no additional array sorts could improve the performance because the runs involved are steadily growing in lengthand thus they always remain larger than the available main store as resultwe may fortunately concentrate our attention on improving the algorithm that generates initial runs naturallywe immediately concentrate our search on the logarithmic array sorting methods the most suitable of them is the tree sort or heapsort method (see sect the heap may be regarded as funnel through which all items must passsome quicker and some more slowly the least key is readily picked off the top of the heapand its replacement is very efficient process the action of funnelling component from the input sequence src (rider through full heap onto an output sequence dest (rider may be described simply as followswrite( [ ])read( [ ])sift( - sift is the process described in sect for sifting the newly inserted component down into its proper place note that is the least item on the heap an example is shown in fig the program eventually becomes considerably more complex for the following reasons the heap is initially empty and must first be filled toward the endthe heap is only partially filledand it ultimately becomes empty we must keep track of the beginning of new runs in order to change the output index at the right time