Report Number: CS-TR-76-543
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