Surprising (for me) benchmark results...

[Brian Quinlan]

> There are O(N) sorting algorithms??  I thought that was restricted to
> quantum computation.

Actually, there are O(N) sorting algorithms. Counting sort is O(N). The
algorithm is simple but only works in (small) descrete element spaces. The
following example works with integers:

def sort( A, k ):
    b = []
    c = []
    for i in range(k):
        c.append(0)

    for j in A:
        c[j] += 1

    for i in range(len(c)):
        b += [i] * c[i]

    return b


print sort( [1,2,2,2,2,5,4,3,2,2,2,5], 6 )
>>> [1, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5, 5]

BTW, this isn't an efficient implementation so don't use it or anything :-)