Optimizing the Polyphase Sort

Various dispersion algorithms for the polyphase
sorting procedure are examinedhe optimum 
algorithm based on minimizing the total number of unit
strings read is displayed.  The logic of this 
algorithm is rather complicated; hence, several other
new dispersion algorithms with more straightforward 
logic are presented.  Of the simple dispersion algorithms
discussed, the  Horizontal is best.  It does 
approximately one-fourth to one and one-half percent
less reading and writing than most algorithms in 
use today.  An additional two and one-fourth to three
percent improvement can be achieved by utilizing 
the Modified Optimum Algorithm.  This algorithm is relatively
straightforward, but it requires a fairly 
close estimate of the total number of unit strings before the dispersion begins.

CACM November, 1971

Shell, D. L.

sorting, polyphase sorting, dispersion algorithms,
optimum dispersion algorithm, repetition operator

5.31

CA711103 JB February 2, 1978  11:39 AM

1117	4	2146
1117	4	2146
2017	4	2146
2017	4	2146
2017	4	2146
2146	4	2146
2146	4	2146
2146	4	2146
2146	4	2146
479	4	2146
677	4	2146
860	4	2146
861	4	2146
862	4	2146
863	4	2146
299	5	2146
2146	5	2146
2146	5	2146
2146	5	2146
862	5	2146
863	5	2146
861	5	2146