# 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 } } }