Length of strings for a merge sort
- 1 November 1963
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 6 (11) , 685-688
- https://doi.org/10.1145/368310.368397
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.Keywords
This publication has 1 reference indexed in Scilit:
- Read-backward polyphase sortingCommunications of the ACM, 1963