Article,
Implementing HEAPSORT with (n logn - 0.9n) and QUICKSORT with (n logn + 0.2n) comparisons
J. Exp. Algorithmics, (December 2002)
DOI: 10.1145/944618.944623
Abstract
With refinements to the <i>WEAK-HEAPSORT</i> algorithm we establish the general and practical relevant sequential sorting algorithm <i>INDEX-WEAK-HEAPSORT</i> with exactly <i>n</i>⌈log <i>n</i>⌉ - 2<sup>⌈log <i>n</i>⌉</sup> + 1 ≤ <i>n</i> log <i>n</i>-0.9<i>n</i> comparisons and at most <i>n</i> log <i>n</i> + 0.1<i>n</i> transpositions on any given input. It comprises an integer array of size <i>n</i> and is best used to generate an index for the data set. With <i>RELAXED-WEAK-HEAPSORT</i> and <i>GREEDY-WEAK-HEAPSORT</i> we discuss modifications for a smaller set of pending element transpositions.If extra space to create an index is not available, with <i>QUICK-WEAK-HEAPSORT</i> we propose an efficient <i>QUICKSORT</i> variant with <i>n</i> log <i>n</i> + 0.2<i>n</i> + <i>o(n)</i> comparisons on the average. Furthermore, we present data showing that <i>WEAK-HEAPSORT, INDEX-WEAK-HEAPSORT</i> and <i>QUICK-WEAK-HEAPSORT</i> compete with other performant <i>QUICKSORT</i> and <i>HEAPSORT</i> variants.
