Quicksort in Python

quicksort.py

#!/usr/bin/env python

"""
An implementation in python, inspired by the version in "Learn You
a Haskell for Great Good!"
(http://learnyouahaskell.com/recursion#quick-sort)

"""

def quicksort (a):
    if len(a) < 2:
        return a
    else:
        p = a[0]
        l = quicksort(filter(lambda x: x <= p, a[1:]))
        r = quicksort(filter(lambda x: x > p,  a[1:]))
        return l + [p] + r
        
        
"""
Test it, using the example arrays from the text:

1 - a numeric array
2 - a string (array of chars)
"""

narr = [10,2,5,3,1,6,7,4,2,3,4,8,9]
nexp = [1,2,2,3,3,4,4,5,6,7,8,9,10]

nres = quicksort(narr)
print 'sorting', narr, '->', nres
assert nres == nexp, 'expected ' + nexp + ' from sorting ' + narr + ' but got ' + nres

# using list() to keep the type system happy
sarr = list("the quick brown fox jumps over the lazy dog")
sexp = list("        abcdeeefghhijklmnoooopqrrsttuuvwxyz")

sres = quicksort(sarr)
print 'sorting "' + ''.join(sarr) + '" -> "' + ''.join(sres) + '"'
assert sres == sexp, 'expected "' + ''.join(sexp) + '" from sorting "' + ''.join(sarr) + '" but got "' + ''.join(sres) + '"'