Given an array A. of N elements the result of sorting the array in place is to arrange elements of A. so that
Heapsort by J. W. J. Williams is a sorting algorithm in place whose worst-case running time is O(N*lgN) on an input array of N items.
A good implementation of QUICKSORT usually beats HEAPSORT in practice. On average the number of comparisons done in HEAPSORT is about twice as much as in QUICKSORT, but HEAPSORT avoids the slight possibility of a catastrophic degradation of performance. The following table compares four sorting algorithms. The A. array includes integers in the range 1 to Max=100,1000,40000,99999.
Unit: nonrecursive internal subroutine
Global variables: array A. of arbitrary elements
Parameter: a positive integer N - number of elements in A.
Result: Reordering of input array such that
Wirth N. Algorithms and data structure
New Jersey, Prentice Hall, Inc., Engelwood Cliffs, 1986
I changed the test from Max=10 ... 40000 to Max=100 ... 99999. Thanks for idea go to Walter Pachl.
This test ran in the Windows 2000 Professional environment on the computer with 132MB RAM and processor x86Family 6 Mode 6 Stepping 5.
James Barbetti sent me the HEAPSORT_RADIX3 subprogram written in Visual Basic. His comment follows: Instead of ~ 2*N*log(N)/log(2) comparisons and moves you get ~ 2*log(N)/log(3) + 2*N comparisons on average; and ~ N*log(N)/log(3) + N moves on average
Thanks for interesting (more theoretically) code go to James Berbetti.