@article{ede-sti-02-hqsort,
  author = {Stefan Edelkamp and Patrick Stiegeler},
  title = {Implementing {HEAPSORT} with $n \log n - 0.9n$ and {QUICKSORT} with $n \log n + 0.2n$ Comparisons}, 
  journal = {The ACM Journal of Experimental Algorithmics},
  volume = {7},
  pages = {article 5},
  year = 2002,
  url = {http://www.jea.acm.org/2002/EdelkampHeapsort/},
  abstract = {With refinements to the weak-heap-sort algorithm we establish the general and practically relevant sequential sorting algorithm index-weak-heap-sort with exactly $n \lceil\log n\rceil - 2^{\lceil \log n\rceil} +1 \leq n \log n - 0.9 n$ comparisons and at most $n \log n + 0.1 n$ transpositions on any given input. It comprises an integer array of size $n$ and is best used to generate an index for the data set. With relaxed-weak-heap-sort and greedy-weak-heap-sort we discuss modifications for a smaller set of pending element transpositions. \par If extra space to create an index is not available, with quick-weak-heap-sort we propose an efficient quicksort variant with $n \log n + 0.2 n + o(n)$ comparisons on the average. Furthermore, we present data showing that weak-heap-sort, index-weak-heap-sort, and quick-weak-heap-sort compete with other performant quicksort and heapsort variants.}
}