Implementing HEAPSORT with ( n log n - 0.9 n ) and QUICKSORT with ( n log n + 0.2 n ) comparisons
Stefan Edelkamp, Patrick Stiegeler · ACM Journal of Experimental Algorithmics · 2002
With refinements to the WEAK-HEAPSORT algorithm we establish the general and practical relevant sequential sorting algorithm INDEX-WEAK-HEAPSORT with exactly n ⌈log n ⌉ - 2 ⌈log n ⌉ + 1 ≤ 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-HEAPSORT and GREEDY-WEAK-HEAPSORT we discuss modifications for a smaller set of pending element transpositions.If extra space to create an index is not available, with QUICK-WEAK-HEAPSORT 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-HEAPSORT, INDEX-WEAK-HEAPSORT and QUICK-WEAK-HEAPSORT compete with other performant QUICKSORT and HEAPSORT variants.