Heapsort

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, heapsort is an efficient, <a href="/facts/Comparison_sort/X1PvE50c">comparison-based</a> <a href="/facts/Sorting_algorithm/PwHpj1Gs">sorting algorithm</a> that reorganizes an input array into a <a href="/facts/Heap_(data_structure)/A67B0K7L">heap</a> (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.
Although somewhat slower in practice on most machines than a well-implemented <a href="/facts/Quicksort/1BeqhLAH">quicksort</a>, it has the advantages of very simple implementation and a more favorable worst-case <a href="/facts/Big_O_notation/weFFjSWg">O(n log n)</a> 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 <a href="/facts/In-place_algorithm/Ghe2PJUF">in-place algorithm</a>, but it is not a <a href="/facts/Stable_sort/PwHpj1Gs">stable sort</a>.
Heapsort was invented by <a href="/facts/J._W._J._Williams/VIJdvrJ8">J. W. J. Williams</a> in 1964. The paper also introduced the <a href="/facts/Binary_heap/YPJAEN94">binary heap</a> as a useful data structure in its own right. In the same year, <a href="/facts/Robert_W._Floyd/sTFRb3TH">Robert W. Floyd</a> published an improved version that could sort an array in-place, continuing his earlier research into the <a href="/facts/Treesort/t3PnVBnK">treesort</a> algorithm.

Heapsort open-in-new

Heapsort