Editing Heapsort (section)

== Comparison with other sorts ==
Heapsort primarily competes with [[quicksort]], another very efficient general purpose in-place unstable comparison-based sort algorithm.

Heapsort's primary advantages are its simple, non-[[Recursion (computer science)|recursive]] code, minimal auxiliary storage requirement, and reliably good performance: its best and worst cases are within a small constant factor of each other, and of the [[Comparison sort#Number of comparisons required to sort a list|theoretical lower bound on comparison sorts]]. While it cannot do better than {{math|''O''(''n'' log ''n'')}} for pre-sorted inputs, it does not suffer from quicksort's {{math|''O''(''n''<sup>2</sup>)}} worst case, either.

Real-world quicksort implementations use a variety of [[heuristic]]s to avoid the worst case, but that makes their implementation far more complex, and implementations such as [[introsort]] and pattern-defeating quicksort<ref>{{cite arXiv
 |first=Orson R. L. |last=Peters
 |title=Pattern-defeating Quicksort
 |date=9 Jun 2021
 |eprint=2106.05123 |class=cs.DS
}}<br/>{{cite web
 |first=Orson R. L. |last=Peters
 |url=https://github.com/orlp/pdqsort
 |title=pdqsort
 |website=Github
 |access-date=2023-10-02
}}</ref> use heapsort as a last-resort fallback if they detect degenerate behaviour.  Thus, their worst-case performance is slightly worse than if heapsort had been used from the beginning.

Heapsort's primary disadvantages are its poor [[locality of reference]] and its inherently serial nature; the accesses to the implicit tree are widely scattered and mostly random, and there is no straightforward way to convert it to a [[parallel algorithm]].

The worst-case performance guarantees make heapsort popular in [[real-time computing]], and systems concerned with maliciously chosen inputs<ref>{{cite web
 |work=Data Structures and Algorithms
 |title=Comparing Quick and Heap Sorts
 |type=Lecture notes
 |first=John |last=Morris
 |publisher=University of Western Australia<!--Author and web pages relocated to Auckland since-->
 |year=1998
 |url=https://www.cs.auckland.ac.nz/software/AlgAnim/qsort3.html
 |access-date=2021-02-12
}}</ref> such as the Linux kernel.<ref>https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/sort.c#n205 Linux kernel source</ref>  The combination of small implementation and dependably [[Principle of good enough|"good enough"]] performance make it popular in [[embedded system]]s, and generally any application where sorting is not a [[Bottleneck (software)|performance bottleneck]].  {{abbr|E.g.|Exempli gratiā; for example}} heapsort is ideal for sorting a list of [[filename]]s for display, but a [[database management system]] would probably want a more aggressively optimized sorting algorithm.

A well-implemented quicksort is usually 2–3 times faster than heapsort.<ref name=LaMarca99>{{cite journal
 |title=The Influence of Caches on the Performance of Sorting
 |first1=Anthony |last1=LaMarca
 |first2=Richard E. |last2=Ladner |author-link2=Richard E. Ladner
 |journal=Journal of Algorithms |volume=31 |issue=1
 |date=April 1999
 |pages=66–104
 |doi=10.1006/jagm.1998.0985
 |citeseerx=10.1.1.456.3616 <!--10.1.1.155.4400 is the 26-page conference version (Fig. 5c on p. 23) and 10.1.1.84.8929 is a shorter 10-page version (Fig. 2c) -->
 |s2cid=206567217 |url=https://www.cs.auckland.ac.nz/~mcw/Teaching/refs/sorting/ladner-lamarca-cach-sorting.pdf
}} See particularly figure 9c on p. 98.</ref><ref>{{cite web
 |title=Sorting by generating the sorting permutation, and the effect of caching on sorting
 |first=Arne |last=Maus
 |author-link=:no:Arne Maus<!--no en page yet-->
 |date=14 May 2014
 |url=https://www.researchgate.net/publication/228620592
}} See Fig. 1 on p. 6.</ref> Although quicksort requires fewer comparisons, this is a minor factor. (Results claiming twice as many comparisons are measuring the top-down version; see {{section link||Bottom-up heapsort}}.) The main advantage of quicksort is its much better locality of reference: partitioning is a linear scan with good spatial locality, and the recursive subdivision has good temporal locality. With additional effort, quicksort can also be implemented in mostly [[branch-free code]],<ref>{{cite journal
 |title=BlockQuicksort: Avoiding Branch Mispredictions in Quicksort
 |first1=Stefan |last1=Edelkamp
 |first2=Armin |last2=Weiß |author-link2=Armin Weiss
 |journal=Journal of Experimental Algorithmics
 |volume=24 |article-number=1.4
 |doi=10.1145/3274660
 |date=30 January 2019
 |arxiv=1604.06697
 |url=https://drops.dagstuhl.de/storage/00lipics/lipics-vol057-esa2016/LIPIcs.ESA.2016.38/LIPIcs.ESA.2016.38.pdf
}}</ref><ref>{{cite conference
 |title=Simple and Fast BlockQuicksort using Lomuto’s Partitioning Scheme
 |first1=Martin |last1=Aumüller  |first2=Nikolaj |last2=Hass
 |conference=Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX)
 |date=7–8 January 2019 |location=San Diego
 |doi=10.1137/1.9781611975499.2 |doi-access=free
 |arxiv=1810.12047
 |url=https://epubs.siam.org/doi/pdf/10.1137/1.9781611975499.2
}}</ref> and multiple CPUs can be used to sort subpartitions in parallel. Thus, quicksort is preferred when the additional performance justifies the implementation effort.

The other major {{math|''O''(''n'' log ''n'')}} sorting algorithm is [[merge sort]], but that rarely competes directly with heapsort because it is not in-place. Merge sort's requirement for {{math|Ω(''n'')}} extra space (roughly half the size of the input<!--Known techniques for reducing this by a small constant factor omitted for simplicity-->) is usually prohibitive except in the situations where merge sort has a clear advantage:
* When a [[stable sort]] is required
* When taking advantage of (partially) pre-sorted input
* Sorting [[linked list]]s (in which case merge sort requires minimal extra space)
* Parallel sorting; merge sort parallelizes even better than quicksort and can easily achieve close to [[linear speedup]]
* [[External sorting]]; merge sort has excellent locality of reference