A generalized polyphase merge algorithm

The k-generalized Fibonacci numbers are defined as in [1]. A polyphase merge (merging an equal number of sequences from k tapes onto a single unused tape) using k+1 tapes is defined in terms of linear combinations of these numbers. A method is described to output sequences onto k of k+1 tapes after the internal sorting of elements to form sequences. This method will permit a polyphase merge of sequences of sorted elements provided that enough sequences are generated internally to place the proper numbers of sequences on each of the k tapes. For each value of k, there is a set of permissible numbers that can represent the total number of sequences generated during the original output process. If one of these numbers is met exactly and if there is a specific distribution of sequences on the k tapes, then a polyphase merge may proceed. If these conditions are not met, an algorithm is necessary to adjust the numbers of sequences to permit a polyphase merge. This paper describes such an algorithm.

View this article in the ACM Digital Library.