Heapsort in Python

What is your favorite sorting algorithm? Mine is heapsort. I love the “implicit bintree” thing… Plus it’s in-place and O(n log n). It doesn’t get much better than that. Here is a Python implementation. I decided to put that on the web because I haven’t found many good examples around.

#!/usr/bin/python

## Implementation of the heapsort algorithm of Robert
## W. Floyd and J.W.J. Williams (1964).
## Python code by Nicolau Werneck <nwerneck@gmail.com>,
## 2010.

## The algorithm needs "1-based" index arrays. This is
## why all list accesses have a "-1".

import random

## This funcion begins from a heap node and moves down
## swapping values when needed, taking the route of the
## largest children.  This could be made into a
## recursive tail-call function.
def sift_down(arr, root, bottom):
    while root*2 <= bottom:
        if root*2 == bottom:
            newr = root*2
        elif arr[root*2-1]>arr[root*2]:
            newr = root*2
        else:
            newr = root*2 + 1

        if arr[root-1] < arr[newr-1]:
            arr[root-1], arr[newr-1] = arr[newr-1], arr[root-1]
            root=newr
        else:
            break

## Generate random (hopefuly unsorted) list of integers.
arr=[random.randint(0,1000) for k in range(100)]

## Generate solution to test.
sol=arr[:]
sol.sort()  ## This is an in-place sort, like heapsort is.

## First step: "Heapify". Move from bottom up enforcing
## heap restriction.
for i in range( len(arr)/2,  0, -1 ):
    sift_down(arr, i, len(arr))

## Second step: Build the sorted list. Repeat for each
## list element:
for i in range( len(arr), 0, -1 ):
    ## Swap heap top (largest) and end. End becomes a
    ## new element of the final sorted list.
    arr[i-1], arr[0] = arr[0], arr[i-1]
    ## Fix heap, moving new top to a correct position
    ## and bringing next largest value to the top.
    sift_down(arr, 1, i-1)

## Test if result is correct
assert sol==arr