Institution: Stanford University, Department of Computer Science

Title: Optimal polyphase sorting

Author: Z ave, Derek A.

Date: March 1976

Abstract: A read-forward polyphase merge algorithm is described which performs the polyphase merge starting from an arbitrary string distribution. This algorithm minimizes the volume of information moved. Since this volume is easily computed, it is possible to construct dispersion algorithms which anticipate the merge algorithm. Two such dispersion techniques are described. The first algorithm requires that the number of strings to be dispersed be known in advance; this algorithm is optimal. The second algorithm makes no such requirement, but is not always optimal. In addition, performance estimates are derived and both algorithmns are shown to be asymptotically optimal.

http://i.stanford.edu/pub/cstr/reports/cs/tr/76/543/CS-TR-76-543.pdf