Heapsort PROBLEM
Given an array A. of N elements the result of sorting the array in place is to arrange elements of A. so that
A.1<=A.2<=...<=A.N ALGORITHM
Heapsort by J. W. J. Williams is a sorting algorithm in place whose worstcase running time is O(N*lgN) on an input array of N items.
PRACTICE
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.
IMPLEMENTATION
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 A.1<=A.2<=...<=A.N
CONNECTIONS
Literature Wirth N. Algorithms and data structure New Jersey, Prentice Hall, Inc., Engelwood Cliffs, 1986
Acknowledgement I changed the test from Max=10 ... 40000 to Max=100 ... 99999. Thanks for idea go to Walter Pachl.
Note This test ran in the Windows 2000 Professional environment on the computer with 132MB RAM and processor x86Family 6 Mode 6 Stepping 5.
Acknowledgement Thanks for interesting (more theoretically) code go to James Berbetti.
