def qsort(L): if len(L) <= 1: return L return qsort( [ lt for lt in L[1:] if lt < L[0] ] ) + \ [ L[0] ] + qsort( [ ge for ge in L[1:] if ge >= L[0] ] ) # IMHO this is almost as nice as the Haskell version from www.haskell.org: # qsort [] = [] # qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x # where # elts_lt_x = [y | y <- xs, y < x] # elts_greq_x = [y | y <- xs, y >= x] # And here's a test function: def qs_test(length): import random joe = range(length) random.shuffle(joe) qsJoe = qsort(joe) for i in range(len(qsJoe)): assert qsJoe[i] == i, 'qsort is broken!'