Heapsort

Files:  sort.c, sort.h

Heapsort sorts an using sift-up heap operations.  The array must first be
ordered into a binary heap.  Let array indexing start at 1.  Array entry i has
child entries 2i and 2i+1, and a parent entry at i div 2 (if i > 1).  Thus, the
array holds a binary tree structure, with the root of the binary tree stored at
entry 1.  If heapsort is to sort the array into ascending order, we require
that child entries in the array are not smaller than the parent entry.  The
build_heap process uses sift-up operations to order the array into a heap:

build_heap {
   for i = n div 2 downto 1 {
       siftup(i, n);
   }
}

The siftup operation reorders the heap when an entry in the array violates heap
order.  When entry p violates heap order, sift-up adjusts the subtree rooted at
p until heap order is satisfied.  Parameter q specifies the end of the subtree.
Let the value of entry p be y.  The child entry, k, with the larger key moves
up one level in the heap to entry p.  If y can not be placed in entry k without
violating heap order, the same process occurs from entry k.  The siftup process
stops when y finds its position.  

siftup(p, q) {
    y = a[p];
    j = p;
    k = 2 * p;

    while k <= q {
        z = a[k];

        if k < q {
            if z < a[k+1] {
                 k = k + 1;
                 z = a[k];
            }
        }

        if(y >= z) break;

        a[j] = z;
        j = k;
        k = 2 * j;
    }
}


Once the array has been ordered into a heap sorting can occur.  Array entries 1
to i are in the heap.  The reminder of the array, after entry i is the sorted
part.  To increase the size of the sorted part, the largest array element,
a[1], is swapped with the last heap entry in array, a[i], and i is decreased by
i.  Note that after swapping, sift-up must occur since a[1] may violate heap
order.

main program {
    build_heap;
    for i = n downto 2 {
        swap(a[1], a[i]);
        siftup(1, i - 1);
    }
}

In the source file, sort.c, the whole sorting process is implemented within the
function heapsort(), including sift-up operations, but the basic structure of
the algorithm remains the same.  Note, for siftup operations during the stage
when the heap is sorted, that the new root node comes from the bottom of the
heap, so it is likely that sift-up will return it to the bottom of the heap.
The sift-up process is implemented efficiently for this by sifting up until the
bottom of the heap is reached and then performing a few sift-down steps.  This
way, only one key comparison is spent during each step in sift-up.