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