CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20161116-173245519

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

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20161116-173245519

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/368310.368397DOIArticle
http://dl.acm.org/citation.cfm?doid=368310.368397PublisherArticle
Additional Information:© 1963 ACM.
Issue or Number:11
DOI:10.1145/368310.368397
Record Number:CaltechAUTHORS:20161116-173245519
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20161116-173245519
Official Citation:Donald E. Knuth. 1963. Length of strings for a merge sort. Commun. ACM 6, 11 (November 1963), 685-688. DOI=http://dx.doi.org/10.1145/368310.368397
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:72081
Collection:CaltechAUTHORS
Deposited By:INVALID USER
Deposited On:17 Nov 2016 20:09
Last Modified:11 Nov 2021 04:55

Repository Staff Only: item control page