## heapsort

 swMATH ID: 34903 Software Authors: Williams JWJ Description: Algorithm 232 heapsort. wikipedia: In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region. Unlike selection sort, heapsort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a heap data structure to more quickly find the largest element in each step.[1]. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but it is not a stable sort. Heapsort was invented by J. W. J. Williams in 1964.[2] This was also the birth of the heap, presented already by Williams as a useful data structure in its own right.[3] In the same year, R. W. Floyd published an improved version that could sort an array in-place, continuing his earlier research into the treesort algorithm Homepage: https://en.wikipedia.org/wiki/Heapsort Related Software: Quicksort; MA57; HSL; HSL_MA87; GALAHAD; Algorithm 97; OR-Library; Find; AS 266; Julia; Algorithm 447; LAPACK; SteinLib; Qhull; gmp; k.c; MersenneTwister; Mathematica; DQP; HSL_MA77 Referenced in: 61 Publications
all top 5

### Referenced by 97 Authors

 8 Katajainen, Jyrki 6 Elmasry, Amr 3 Edelkamp, Stefan 3 Gould, Nicholas Ian Mark 3 Letchford, Adam N. 3 Vahrenhold, Jan 2 Carlsson, Svante 2 Fagerberg, Rolf 2 Jensen, Claus 2 Munro, J. Ian 2 Sack, Jörg-Rüdiger 1 Akar, Mehmet 1 Bernstein, Daniel Julius 1 Bille, Philip 1 Blunck, Henrik 1 Boyar, Joan F. 1 Brass, Peter 1 Brazil, Marcus N. 1 Brönnimann, Hervé 1 Browne, Philip A. 1 Buchbinder, Niv 1 Budd, Christopher John 1 Chen, Jingsen 1 Chen, Pin-Liang 1 Cihan, Onur 1 Dijkstra, Edsger Wybe 1 Ding, Yuzheng 1 Doberkat, Ernst-Erich 1 Du, Min-Wen 1 Dutton, Ronald D. 1 Erkan, Ö. Feyza 1 Fredman, Michael L. 1 Gajdoš, Jozef 1 Gambosi, Giorgio 1 Gamby, Ask Neve 1 Geffert, Viliam 1 Gonzalez, Teofilo F. 1 Gørtz, Inge Li 1 Guénoche, E. 1 Gutin, Gregory Z. 1 Han, Wook-Shin 1 Hansen, Pierre 1 Hasham, Alnoor 1 Hsieh, Sun-Yuan 1 Iacono, John 1 Jaumard, Brigitte 1 Johnson, Donald B. 1 Kaparis, Konstantinos 1 Khoong, C. M. 1 Kim, H. Alicia 1 Kim, Jinha 1 Kim, Sungchul 1 Klein, Shmuel Tomi 1 Lange, Kenneth L. 1 Larsen, Kim Skak 1 Lee, Chia-Wei 1 Mattsson, Christer 1 Miller, Sebastian J. 1 Minoux, Michel Andre 1 Moffat, Alistair 1 Morin, Pat 1 Morrison, Jason 1 Nardelli, Enrico 1 Navarro, Gonzalo 1 Oh, Jinoh 1 Pacheco, Joaquín A. 1 Paessens, H. 1 Paredes, Rodrigo 1 Paul, Gerald 1 Paulik, Augustin 1 Pearson, Nicholas A. 1 Petrank, Erez 1 Piotrów, Marek 1 Ras, Charl J. 1 Robinson, Daniel P. 1 Sedgewick, Robert 1 Sevcik, Carlos 1 Skjoldjensen, Frederik Rye 1 Srikanthan, Thambipillai 1 Stølting Brodal, Gerth 1 Strothotte, Thomas W. 1 Suwanda, Hendra 1 Takaoka, Tadao 1 Talamo, Maurizio 1 Tarjan, Robert Endre 1 Thomas, Doreen Anne 1 Toint, Philippe L. 1 Toussaint, Godfried T. 1 Valencia, Olga 1 van Gasteren, Antonetta Johanna Maria 1 Volz, Marcus 1 Wang, Guojin 1 Weiss, Mark Allen 1 Wu, Jigang 1 Xin, Shiqing 1 Yeo, Anders 1 Yu, Hwanjo
all top 5

### Referenced in 30 Serials

 12 Information Processing Letters 5 Theoretical Computer Science 3 Acta Informatica 3 BIT 3 Journal of Computer and System Sciences 3 Algorithmica 2 Discrete Applied Mathematics 2 Information Sciences 2 Information and Computation 2 Mathematical Programming. Series A. Series B 2 Computational Optimization and Applications 2 Theory of Computing Systems 2 Journal of Discrete Algorithms 1 Journal of Computational Physics 1 Journal of the Franklin Institute 1 Mathematics of Computation 1 Computing 1 International Journal for Numerical Methods in Engineering 1 Journal of Optimization Theory and Applications 1 Journal of Classification 1 Applied Numerical Mathematics 1 Computers & Operations Research 1 Computational Geometry 1 European Journal of Operational Research 1 Computational Statistics and Data Analysis 1 Experimental Mathematics 1 Discrete Optimization 1 Science in China. Series F 1 Algorithms 1 Other Titles in Applied Mathematics
all top 5

### Referenced in 15 Fields

 47 Computer science (68-XX) 14 Operations research, mathematical programming (90-XX) 4 Combinatorics (05-XX) 4 Numerical analysis (65-XX) 3 Number theory (11-XX) 3 Convex and discrete geometry (52-XX) 2 Statistics (62-XX) 2 Information and communication theory, circuits (94-XX) 1 General and overarching topics; collections (00-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Probability theory and stochastic processes (60-XX) 1 Mechanics of deformable solids (74-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Biology and other natural sciences (92-XX) 1 Systems theory; control (93-XX)