Editing Heapsort (section)

{{Short description|A sorting algorithm which uses the heap data structure}}
{{Use dmy dates|date=March 2022}}
{{Infobox Algorithm|class=[[Sorting algorithm]]
|image=[[File:Sorting heapsort anim.gif]]
|caption=A run of heapsort sorting an array of randomly permuted values. In the first stage of the algorithm the array elements are reordered to satisfy the [[Heap (data structure)|heap property]]. Before the actual sorting takes place, the heap tree structure is shown briefly for illustration.
|data=[[Array data structure|Array]]
|time=<math>O(n\log n)</math>
|average-time=<math>O(n\log n)</math>
|best-time=<math>O(n\log n)</math> (distinct keys)<ref>{{cite journal
 |journal=Journal of Algorithms
 |volume=20 |number=11
 |pages=205–217
 |year=1996
 |title=On the Best Case of Heapsort
 |first1=B. |last1=Bollobás
 |first2=T. I. |last2=Fenner
 |first3=A. M. |last3=Frieze
 |doi=10.1006/jagm.1996.0011 |url=https://www.math.cmu.edu/~af1p/Texfiles/Best.pdf
}}</ref><ref>{{cite tech report
 |title=The Best Case of Heapsort
 |institution=Princeton University
 |number=TR-293-90
 |last1=Sedgewick |first1=Robert |authorlink1=Robert Sedgewick (computer scientist)
 |last2=Schaffer |first2=Russel W.
 |date=October 1990
 |url=https://www.cs.princeton.edu/research/techreps/TR-293-90
}}</ref><br />or <math>O(n)</math> (equal keys)
|space=<math>O(n)</math> total <math>O(1)</math> auxiliary
}}
In [[computer science]], '''heapsort''' is an efficient, [[comparison sort|comparison-based]] [[sorting algorithm]] that reorganizes an input array into a [[heap (data structure)|heap]] (a data structure where each node is greater than its children) and then repeatedly removes the largest node from that heap, placing it at the end of the array in a similar manner to [[Selection sort]]. <ref>{{Cite book |last=Cormen |first=Thomas H. |title=Introduction to algorithms |last2=Leiserson |first2=Charles Eric |last3=Rivest |first3=Ronald L. |last4=Stein |first4=Clifford |date=2022 |publisher=The MIT Press |isbn=978-0-262-04630-5 |edition=4th|location=Cambridge, Massachusetts |pages=170}}</ref>

Although somewhat slower in practice on most machines than a well-implemented [[quicksort]], it has the advantages of very simple implementation and a more favorable worst-case {{math|[[big O notation|''O''(''n'' log ''n'')]]}} runtime.  Most real-world quicksort variants include an implementation of heapsort as a fallback should they detect that quicksort is becoming degenerate. Heapsort is an [[in-place algorithm]], but it is not a [[stable sort]].

Heapsort was invented by [[J. W. J. Williams]] in 1964.<ref>{{harvnb|Williams|1964}}</ref> The paper also introduced the [[binary heap]] as a useful data structure in its own right.<ref name="brass">{{cite book |first=Peter |last=Brass |title=Advanced Data Structures |publisher=Cambridge University Press |year=2008 |isbn=978-0-521-88037-4 |page=209}}</ref> In the same year, [[Robert W. Floyd]] published an improved version that could sort an array in-place, continuing his earlier research into the [[treesort]] algorithm.<ref name="brass"/>