I wrote an implementation of quicksort that I think is pythonic. I based it off of this common Haskell implementation:
quicksort :: (Ord a) => [a] -> [a] quicksort  =  quicksort (x:xs) = let smallerSorted = quicksort [a | a <- xs, a <= x] biggerSorted = quicksort [a | a <- xs, a > x] in smallerSorted ++ [x] ++ biggerSorted
I understand this is not an in-place sort. I also understand that it is optimized for Haskell, which handles recursion very well.
Here's my Python adaptation:
def quicksort(li): if li == : return li p = li lo = [ i for i in li[1:] if i <= p ] hi = [ i for i in li[1:] if i > p ] return quicksort(lo) + [p] + quicksort(hi)
I think it has the following upsides:
- clean looking, pythonic
- fast C implementation of linear partitioning
and the following downsides:
- does not sort in place
- possibly memory inefficient
What are some issues I should be aware of besides the above? Can the algorithm be improved in terms of memory complexity without sacrificing the simplicity and pythonic structure? Should I avoid recursion altogether? Does anyone see bugs or have proposed changes?