Heapsort

Heapsort is a sort algorithm that works as follows:

• make a heap of the data (O(N))
• remove items from the heap one at a time until the heap is empty (O(N lg N))

It can be performed in place with constant auxiliary storage; the "fixheap" routine given below is recursive, but it's tail-recursive, and therefore can be straightforwardly converted to be iterative. No other O(N lg N) sort can be performed with constant auxiliary storage.

Here's a Python implementation:

def reverserange(n):
    list = range(n)
    list.reverse()
    return list

def fixheap(array, heaplen, index, greaterthan):
    lc = 2 * index + 1  # left child
    rc = lc + 1         # right child
    
    # if the left child is inside the heap and the max of the 3, move it up:
    if (lc < heaplen and greaterthan(array[lc], array[index]) and
            (rc >= heaplen or
            (rc < heaplen and not greaterthan(array[rc], array[lc])))):
        (array[index], array[lc]) = (array[lc], array[index])
        fixheap(array, heaplen, lc, greaterthan)

    # else if the right child is, move it up:
    elif (rc < heaplen and greaterthan(array[rc], array[index]) and 
              greaterthan(array[rc], array[lc])):
        (array[index], array[rc]) = (array[rc], array[index])
        fixheap(array, heaplen, rc, greaterthan)

def makeheap(array, greaterthan):
    for i in reverserange(len(array)/2):
        fixheap(array, len(array), i, greaterthan)

def heapsort(array, cmp=lambda x, y: x > y):
    makeheap(array, cmp)
    for i in reverserange(len(array)):
        (array[i], array[0]) = (array[0], array[i])
        fixheap(array, i, 0, cmp)

/Talk