Fibonacci merge

The idea behind Fibonacci merge is that we want to merge in a sequence of phases, each phase stopping when one tape becomes empty, and the next phase using the (unique) empty tape for its output tape --- for this reason the method is sometimes called polyphase merge. If there are r tapes, then at the end one tape will have a single run on it, and at the start of that phase, each of the other r-1 tapes will have had exactly one run.

We can extend this idea, providing we designate the output tape at the end of each run. It is customary to have the algorithm end on tape 1, and to have had the output tape designated cyclically in previous phases.

For example, if we initially have 82 runs with 4 tapes, we would determine the distribution of runs needed as (think of time as running from bottom to top):

Table 2: Computation of Run Distribution for Fibonacci Merge

Since we need a total number of runs equal to some number in the Total Runs column, we would add 23 dummy runs (consisting of a single record with key infinity) to get a total of 105 runs, and distribute these: 37 runs to tape 1, 44 to tape 2, and 24 to tape 4, with tape 3 as the initial output tape.

The modifications needed to make the merge work are:

1. To keep runs separated, we add a dummy record with key infinity to the end of each run.
2. To prevent accumulation of garbage at the end of each run, we discard all but one of the infinities at the end of the run.
3. To keep dummy runs from being merged, we have to have infinity on a tape always being larger than any value in the heap, even another infinity.