Length of Strings for a Merge Sort

Detailed statistics are given on the length
of maximal sorted strings which result form the 
first (internal sort) phase of a merge sort onto tapes.
 It is shown that the strings produced by an 
alternating method (i.e. one which produces ascending
and descending strings alternately) tend to be 
only three-fourths as long as those in a method which produces
only ascending strings, contrary to statements 
which have appeared previously in the literature.  A
slight modification of the read-backward polyphase 
merge algorithm is therefore suggested.

CACM November, 1963

Knuth, D. E.

CA631115 JB March 13, 1978  3:31 PM

1117	4	677
2017	4	677
2146	4	677
677	4	677
860	4	677
1638	5	677
2176	5	677
2272	5	677
677	5	677
677	5	677
677	5	677
861	5	677
1638	6	677
677	6	677
677	6	677
677	6	677