Subscribe
(Full Service)
Register
(Limited Service,
Free
)
Login
Search:
The ACM Digital Library
The Guide
Feedback
Algorithm 245: Treesort
Full text
Pdf
(348 KB)
Source
Communications of the ACM
archive
Volume 7 , Issue 12 (December 1964)
table of contents
Page: 701
Year of Publication: 1964
ISSN:0001-0782
Author
Robert W. Floyd
Computer Associates, Inc., Wakefield, MA
Publisher
ACM
New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 15, Downloads (12 Months): 87, Citation Count: 43
Additional Information:
cited by
collaborative colleagues
Tools and Actions:
Request Permissions
Review this Article
Save this Article to a Binder
Display Formats:
BibTeX
EndNote
ACM Ref
DOI Bookmark:
Use this link to bookmark this Article:
http://doi.acm.org/10.1145/355588.365103
What is a DOI?
CITED BY
43
W. A. Martin, Sorting, ACM Computing Surveys (CSUR), v.3 n.4, p.147-174, Dec. 1971
Robert E. Noonan, Towards a canonical form for computer programs, Proceedings of the 1975 annual conference, p.235-240, January 1975
Bruce Weide, A Survey of Analysis Techniques for Discrete Algorithms, ACM Computing Surveys (CSUR), v.9 n.4, p.291-313, Dec. 1977
Y. Perl , M. R. Garey , S. Even, Efficient Generation of Optimal Prefix Code: Equiprobable Words Using Unequal Cost Letters, Journal of the ACM (JACM), v.22 n.2, p.202-214, April 1975
R. M. Burstall , John Darlington, Some transformations for developing recursive programs, ACM SIGPLAN Notices, v.10 n.6, p.465-472, June 1975
Wei-Mei Chen , Gen-Huey Chen, Divide-and-conquer recurrences associated with generalized heaps, optimal merge, and related structures, Theoretical Computer Science, v.292 n.3, p.667-677, 31 January 2003
Rudolf Loeser, Some performance tests of “quicksort” and descendants, Communications of the ACM, v.17 n.3, p.143-152, March 1974
Anthony LaMarca , Richard E. Ladner, The influence of caches on the performance of sorting, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.370-379, January 05-07, 1997, New Orleans, Louisiana, United States
Gerth Stølting Brodal, Worst-case efficient priority queues, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.52-58, January 28-30, 1996, Atlanta, Georgia, United States
Michael T. Goodrich , Roberto Tamassia, Teaching the analysis of algorithms with visual proofs, ACM SIGCSE Bulletin, v.30 n.1, p.207-211, Mar. 1998
David S. Burris , Kurt Schember, Sorting sequential files with limited auxiliary storage, Proceedings of the 18th annual Southeast regional conference, March 24-26, 1980, Tallahassee, Florida
Curtis R. Cook , Do Jin Kim, Best sorting algorithm for nearly sorted lists, Communications of the ACM, v.23 n.11, p.620-624, Nov. 1980
Svante Carlsson , Jingsen Chen, The complexity of heaps, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.393-402, September 1992, Orlando, Florida, United States
Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM, v.21 n.4, p.309-315, April 1978
R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977
Jukka Teuhola , Lutz Wegner, Minimal space, average linear time duplicate deletion, Communications of the ACM, v.34 n.3, p.62-73, March 1991
Ellis L. Johnson, On shortest paths and sorting, Proceedings of the ACM annual conference, August 01-01, 1972, Boston, Massachusetts, United States
Richard J. Lipton , Arnold L. Rosenberg , Andrew C. Yao, External Hashing Schemes for Collections of Data Structures, Journal of the ACM (JACM), v.27 n.1, p.81-95, Jan. 1980
Stephen Alstrup , Gerth Brodal , Theis Rauhe, Optimal static range reporting in one dimension, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.476-482, July 2001, Hersonissos, Greece
K. A. Redish, Comment on London's certification of algorithms 245, Communications of the ACM, v.14 n.1, p.50-51, Jan. 1971
Norihisa Suzuki, Verifying programs by algebraic and logical reduction, ACM SIGPLAN Notices, v.10 n.6, p.473-481, June 1975
Ralph L. London, Certification of algorithm 245 [M1]:treesort 3:proof of algorithms—a new kind of certification, Communications of the ACM, v.13 n.6, p.371-373, June 1970
L. Li, Fast In-Place Verification of Data Dependencies, IEEE Transactions on Knowledge and Data Engineering, v.5 n.2, p.266-281, April 1993
Marek Piotrów, A note on constructing binary heaps with periodic networks, Information Processing Letters, v.83 n.3, p.129-134, 16 August 2002
Jing-Chao Chen, Proportion split sort, Nordic Journal of Computing, v.3 n.3, p.271-279, Fall 1996
Biographies, IEEE Annals of the History of Computing, v.26 n.2, p.75-83, April 2004
Lawrence Robinson , Karl N. Levitt, Proof techniques for hierarchically structured programs, Communications of the ACM, v.20 n.4, p.271-283, April 1977
M. D. Atkinson , J.-R. Sack , B. Santoro , T. Strothotte, Min-max heaps and generalized priority queues, Communications of the ACM, v.29 n.10, p.996-1000, Oct. 1986
Gianni Franceschini , Roberto Grossi , J. Ian Munro , Linda Pagli, Implicit B-trees: a new data structure for the dictionary problem, Journal of Computer and System Sciences, v.68 n.4, p.788-807, June 2004
Jesper Bojesen , Jyrki Katajainen , Maz Spork, Performance engineering case study: heap construction, Journal of Experimental Algorithmics (JEA), 5, p.15-es, 2000
F. W von Henke , D. C. Luckham, A methodology for verifying programs, ACM SIGPLAN Notices, v.10 n.6, p.156-164, June 1975
Hervé Brönnimann , John Iacono , Jyrki Katajainen , Pat Morin , Jason Morrison , Godfried Toussaint, Space-efficient planar convex hull algorithms, Theoretical Computer Science, v.321 n.1, p.25-40, June 16, 2004
L. M. Wegner , J. I. Teuhola, The External Heapsort, IEEE Transactions on Software Engineering, v.15 n.7, p.917-925, July 1989
Niv Buchbinder , Erez Petrank, Lower and upper bounds on obtaining history independence, Information and Computation, v.204 n.2, p.291-337, February 2006
Ingo Schmitt , Sören Balko, Filter ranking in high-dimensional space, Data & Knowledge Engineering, v.56 n.3, p.245-286, March 2006
Henrik Weimer , Joe Warren , Jane Troutner , Wendell Wiggins , John Shrout, Efficient co-triangulation of large data sets, Proceedings of the conference on Visualization '98, p.119-126, October 18-23, 1998, Research Triangle Park, North Carolina, United States
Jan Vahrenhold, An in-place algorithm for Klee's measure problem in two dimensions, Information Processing Letters, v.102 n.4, p.169-174, May, 2007
Thomas D. Otto , Andreas M. Thurnherr, Efficient algorithms for finding sills in digital topographic maps, Computers & Geosciences, v.33 n.5, p.678-684, May, 2007
Ward Douglas Maurer, Generalized structured programs and loop trees, Science of Computer Programming, v.67 n.2-3, p.223-246, July, 2007
Jan Vahrenhold, Line-segment intersection made in-place, Computational Geometry: Theory and Applications, v.38 n.3, p.213-230, October, 2007
Thomas Hazel , Laura Toma , Jan Vahrenhold , Rajiv Wickremesinghe, Terracost: Computing least-cost-path surfaces for massive grid terrains, Journal of Experimental Algorithmics (JEA), 12, June 2008
Jeff Parker, Snakes and ladders: patterns in Heapsort, Journal of Computing Sciences in Colleges, v.24 n.2, December 2008
Gerth Stølting Brodal , Rolf Fagerberg , Gabriel Moruz, On the adaptiveness of Quicksort, Journal of Experimental Algorithmics (JEA), 12, June 2008
Collaborative Colleagues:
Robert W. Floyd:
colleagues