An Improved HEAPSORT Algorithm with n log n - 0.788928n Comparisons in the Worst Case

A new variant of HEAPSORT is presented in this paper. The algorithm is not an internalsorting algorithm in the strong sense, since extra storage for nintegers is necessary. The basic idea of the new algorithm is similar tothe classical sorting algorithm HEAPSORT, but the algorithm rebuilds theheap in another way. The basic idea of the new algorithm is it uses onlyone comparison at each node. The new algorithm shift walks down a path inthe heap until a leaf is reached. The request of placing the element inthe root immediately to its destination is relaxed. The new algorithmrequires about n \log n-0.788928n comparisons in the worst case andn\log n-n comparisons on the average which is only about 0.4n morethan necessary. It beats on average even the clever variants ofQUICKSORT, if n is not very small. The difference between the worstcase and the best case indicates that there is still room forimprovement of the new algorithm by constructing heap more carefully.