Algorithms and Complexity
Lecture Notes in Computer Science, 2000, Volume 1767/2000, 150-162, DOI: 10.1007/3-540-46521-9_13

QuickHeapsort, an Efficient Mix of Classical Sorting Algorithms

Domenico Cantone and Gianluca Cincotti

View Related Documents

Abstract

We present a practically efficient algorithm for the internal sorting problem. Our algorithm works in-place and, on the average, has a running-time of O(n log n) in the length n of the input. More specifically, the algorithm performs n log n + 3n comparisons and n log n + 2.65n element moves on the average.
An experimental comparison of our proposed algorithm with the most efficient variants of Quicksort and Heapsort is carried out and its results are discussed.

Keywords  In-place sorting - heapsort - quicksort - analysis of algorithms

Fulltext Preview

Image of the first page of the fulltext document