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: |
| |||||||||
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