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