# heap sort
BEGIN {
for (i=0; i<=20; i++)
tester(i)
tester(1000) }
function tester(i) {
genid(x,i); sort(x,i); check(x,i); clear(x)
gensort(x,i); sort(x,i); check(x,i); clear(x)
genrev(x,i); sort(x,i); check(x,i); clear(x)
genrand(x,i); sort(x,i); check(x,i); clear(x) }
function genid(x,n, i) {
for (i=1; i<=n; i++)
x[i] = 1 }
function gensort(x,n, i) {
for (i=1; i<=n; i++)
x[i] = i }
function genrev(x,n, i) {
for (i=1; i<=n; i++)
x[i] = n + 1 - i }
function genrand(x,n, i) {
for (i=1; i<=n; i++)
x[i] = int(n * rand()) }
function check(x,n, i) {
for (i=1; i<n; i++)
if (x[i+1]+0 < x[i]+0) {
printf "error in sort"
exit } }
function clear(x, i) {
for (i in x)
delete x[i] }
# simple heap sort
function swap(A,i,j, t) {
t = A[i]; A[i] = A[j]; A[j] = t }
function heapify(A,left,right, p,c) {
for (p=left; (c=2*p) <= right; p=c) {
if (c<right && A[c] < A[c+1]) c++
if (A[p] < A[c]) swap(A, c, p) } }
function sort(A,n, i) {
for (i=int(n/2); i>=1; i--)
heapify(A, i, n)
for (i=n; i>1; i--) {
swap(A, 1, i)
heapify(A, 1, i-1) } }
# move swap inline, move invariant part of swap out of inner loop
function heapify(A,left,right, p,c,t) {
t = A[left]
for (p=left; (c=2*p) <= right; p=c) {
if (c<right && A[c] < A[c+1]) c++
if (t < A[c]) A[p] = A[c]; else break }
A[p] = t }
function sort(A,n, i,t) {
for (i=int(n/2); i>=1; i--)
heapify(A, i, n)
for (i=n; i>1; i--) {
t = A[1]; A[1] = A[i]; A[i] = t
heapify(A, 1, i-1) } }
# sift all the way down, then back up
function heapify(A,left,right, p,c,t) {
t = A[left]
for (p=left; (c=2*p) <= right; p=c) {
if (c<right && A[c] < A[c+1]) c++
A[p] = A[c] }
for (c=p; (p=int(c/2)) >= left; c=p) {
if (t > A[p]) A[c] = A[p]; else break }
A[c] = t }
function sort(A,n, i,t) {
for (i=int(n/2); i>=1; i--)
heapify(A, i, n)
for (i=n; i>1; i--) {
t = A[1]; A[1] = A[i]; A[i] = t
heapify(A, 1, i-1) } }
# move heapify code inline
function sort(A,n, l,r,p,c,t) {
if (n > 1) {
l = int(n/2) + 1; r = n
while(1) {
if (l > 1) t = A[--l]
else { t = A[r]; A[r--] = A[1]
if (r == 1) { A[1] = t; return } }
for (p=l; (c=2*p) <= r; p=c) {
if (c < r && A[c] < A[c+1]) c++
A[p] = A[c] }
for (c=p; (p=int(c/2)) >= l; c=p) {
if (A[p] < t) A[c] = A[p]; else break }
A[c] = t } } }