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.
Running time in seconds for N=10000 

Algorithm 
Max = 100 
Max = 1000 
Max = 40000 
Max = 99999 
QUICKSORT 
4.66 
4.53 
4.89 
4.59 
HEAPSORT 
10.26 
10.67 
11.58 
11.18 
SHELLSORT 
7.45 
8.89 
10.58 
10.13 
COUNTING_SORT 
1.88 
1.95 
7.93 
31.85 
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
HEAPSORT: procedure expose A.
parse arg N
do I = N % 2 to 1 by 1
call SIFT I, N
end
do I = N to 2 by 1
W = A.1; A.1 = A.I; A.I = W
call SIFT 1, I  1
end
return
SIFT: procedure expose A.
parse arg L, R
I = L; W = A.I; J = 2 * I
Jp1 = J + 1
if J < R then
if A.J < A.Jp1 then J = Jp1
do while J <= R
if W >= A.J then leave
A.I = A.J; I = J; J = 2 * I
Jp1 = J + 1
if J < R then
if A.J < A.Jp1 then J = Jp1
end
A.I = W
return

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.
HEAPSORT_RADIX3: procedure expose A.
parse arg N
do R = (N+1)%3 to 1 by 1
call SiftDown A.R, N, R
end
do R = N to 2 by 1
V = A.R; A.R = A.1
call SiftDown V, (R  1), 1
end
return
SIFTDOWN: procedure expose A.
V = ARG(1); Count = ARG(2); I = ARG(3)
J = I
do forever
K = J * 3  1
if K < Count  1
then do
Kp1 = K + 1; Kp2 = K + 2
if A.K < A.Kp1 then
if A.Kp1 < A.Kp2 then K = Kp2
else K = Kp1
else if A.K < A.Kp2 then K = Kp2
end
else do
if K < Count
then do
Kp1 = K + 1
if A.K < A.Kp1 then K = Kp1
end
else if Count < K then leave
end
A.J = A.K
J = K
end
K = J
do while K > I
J = (K + 1) % 3
if A.J > V then leave
A.K = A.J
K = J
end
A.K = V
return

Acknowledgement Thanks for interesting (more theoretically) code go to James Berbetti.
