BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small) (Q688722)

Consider the following variant of heapsort: after the heap has been built and the root is extracted, the heap is reconstructed by positioning the rightmost leaf from the bottom properly on a special path. This path is determined (through the call to a procedure leaf-search) iteratively by taking the smallest son; it ends in a leaf called the special leaf. The position the rightmost leaf will be inserted in may be determined by searching the special path bottom-up; once this position has been identified, the element may be inserted without further comparisons. This idea works also for heap construction. The author analyzes this variant of heapsort (which he calls BOTTOM-UP-HEAPSORT) for some aspects of the worst and the average case, resp.: the worst case number of comparisons for the calls to leaf-search during the selection phase is shown to be \(n \bigl\lfloor \log(n-2) \bigr\rfloor-2 \times 2^{\lfloor \log(n-2) \rfloor}- \bigl\lfloor \log(n-2) \bigr\rfloor +2\), the average case of comparisons for the heap creation phase is \((9/2-\alpha_ 1-\alpha_ 2- \beta)n+\Theta(\log n)\) \(\biggl(\) putting \(\alpha_ i:=\sum_{j \geq 1}1/(2^ j-1)^ i\), \(\beta :=\sum_{j \geq 2}1/ \bigl( 2^ j(2^ j-1) \bigr) \biggr)\) with the average number of assignment during this phase as \((\alpha_ 1+\alpha_ 2-1-2 \beta)n+\Theta(\log n)\). These results make use of this reviewer's average case analysis of Floyd's algorithm for heap creation, and of a first deletion from a random heap [\textit{E. E. Doberkat}, Acta Inf. 17, 245-265 (1982; Zbl 0487.68029) and Int. Control 61, 114-131 (1984; Zbl 0589.68046)]. The paper also discusses some aspects for the analysis of the selection phase of heapsort and concludes by showing that BOTTOM-UP-HEAPSORT does not need more than \(1.5n \log(n)+{\mathcal O}(n)\) comparisons. The results obtained are compared to those for a variant of Quicksort, accounting for the somewhat catchy title.