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
