pythonでquicksort

Learn You Haskell for Great Goodに出てくるquicksortを，リスト内包や再帰もそのままでpythonで作成。ただそれだけなんだけど，いつか何かの役に立つかもしれないので一応残しておこう。

def quicksort(x):
    if x==[]: return []

    smallerSorted = quicksort([a for a in x[1:] if a <= x[0]])
    biggerSorted = quicksort([a for a in x[1:] if a > x[0]])

    return(smallerSorted+[x[0]]+biggerSorted)

x = [10,2,5,3,1,6,7,4,2,3,4,8,9]
print(quicksort(x))

実行結果

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