sequences as uniformly as possiblesince we are interested in active merges from as many sources as possible let us forget dummy runs for moment and consider the problem of distributing an unknown number of runs onto - sequences it is plain that the fibonacci numbers of order - specifying the desired numbers of runs on each source can be generated while the distribution progresses assumingfor examplen and referring to table we start by distributing runs as indicated by the row with index ( )if there are more runs availablewe proceed to the second row ( )if the source is still not exhaustedthe distribution proceeds according to the third row ( )and so on we shall call the row index level evidentlythe larger the number of runsthe higher is the level of fibonacci numbers whichincidentallyis equal to the number of merge passes or switchings necessary for the subsequent sort the distribution algorithm can now be formulated in first version as follows let the distribution goal be the fibonacci numbers of order - level distribute according to the set goal if the goal is reachedcompute the next level of fibonacci numbersthe difference between them and those on the former level constitutes the new distribution goal return to step if the goal cannot be reached because the source is exhaustedterminate the distribution process the rules for calculating the next level of fibonacci numbers are contained in their definition we can thus concentrate our attention on step wherewith given goalthe subsequent runs are to be distributed one after the other onto the - output sequences it is here where the dummy runs have to reappear in our considerations let us assume that when raising the levelwe record the next goal by the differences di for - where di denotes the number of runs to be put onto sequence in this step we can now assume that we immediately put di dummy runs onto sequence and then regard the subsequent distribution as the replacement of dummy runs by actual runseach time recording replacement by subtracting from the count di thusthe di indicates the number of dummy runs on sequence when the source becomes empty it is not known which algorithm yields the optimal distributionbut the following has proved to be very good method it is called horizontal distribution (cf knuthvol ) term that can be understood by imagining the runs as being piled up in the form of silosas shown in fig for level (cf table in order to reach an equal distribution of remaining dummy runs as quickly as possibletheir replacement by actual runs reduces the size of the piles by picking off dummy runs on horizontal levels proceeding from left to right in this waythe runs are distributed onto the sequences as indicated by their numbers as shown in fig fig horizontal distribution of runs