Length of strings for a merge sort

ABSTRACT

Detailed statistics are given on the length of maximal sorted strings which result from 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.

REFERENCES

• 1: GABSNER, B. J. Proof of a conjecture concerning sorting by replacement selection. Unpublished paper, 1958; presented at ACM Nat. Conf., Syracuse, 1963.
• 2: R. L. Gilstad, Read-backward polyphase sorting, Communications of the ACM, v.6 n.5, p.220-223, May 1963 [doi>10.1145/366552.366562]
• 3: MACMAHON, P. A. Combinatory Analysis. Ch. 4, 5. Cambridge, 1915.