Python implementation of Quicksort using list comprehensions

Question

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[0]
    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?

Answer 1

IMHO you can't really compare in-place quicksort to not-in-place quicksort. While the basic algorithm is the same, the implementation is vastly different, one being in-place (d'uh) and the other being much, much simpler.

Having said that, you could make your code a bit faster and (IMHO) cleaner by a) using wildcard-unpacking to separate the pivot from the rest (no need to slice the list twice), and b) return the list itself if it contains zero or one elements (no need to partition a one-elemented list).

def quicksort(lst):
    if len(lst) <= 1:
        return lst
    else:
        p, *rest = lst
        low  = [x for x in rest if x <= p]
        high = [x for x in rest if x >  p]
        return quicksort(low) + [p] + quicksort(high)

The else is kind of redundant here, but IMHO it's cleaner that way.

However, using the first element of the list as pivot can be problematic if the list is already (partially) sorted, which is not uncommon. In this case, the performance will be much better/more predictable using a randomly chosen pivot (or any other method). This means that we have to partition the list into three parts, though, low, med, and high, otherwise we risk getting infinite recursion in case the list contains two or more copies of the pivot.

def quicksort(lst):
    if len(lst) <= 1:
        return lst
    else:
        p = random.choice(lst)
        low  = [x for x in lst if x <  p]
        med  = [x for x in lst if x == p]
        high = [x for x in lst if x >  p]
        return quicksort(low) + med + quicksort(high)