A Caltech Library Service

Length of strings for a merge sort

Knuth, Donald E. (1963) Length of strings for a merge sort. Communications of the ACM, 6 (11). pp. 685-688. ISSN 0001-0782. doi:10.1145/368310.368397.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 1963 ACM.
Issue or Number:11
Record Number:CaltechAUTHORS:20161116-173245519
Persistent URL:
Official Citation:Donald E. Knuth. 1963. Length of strings for a merge sort. Commun. ACM 6, 11 (November 1963), 685-688. DOI=
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:72081
Deposited On:17 Nov 2016 20:09
Last Modified:11 Nov 2021 04:55

Repository Staff Only: item control page