Fun with fancy slicing

[David Eppstein]

In article <ueEeb.206007$R32.6624508 at news2.tin.it>,
 Alex Martelli <aleax at aleax.it> wrote:

> Dave Benjamin wrote:
>     ...
> > of the trademark quicksort implementation in Haskell, ie. it may not be
> > great in practice, but you can see the algorithm at a high level which
> > makes it easier to figure out what's going on.
> 
> Hmmm, you mean as in...:
> 
> def quicksort(alist):
>     head = alist[0]
>     return quicksort([ x in alist[1:] if x<=head ]) + [
>         head ] + quicksort([ x in alist[1:] if x>head ])
> 
> ...?

Well, except that it gets a syntax error.  And if you correct the syntax 
it gets an IndexError due to the lack of a base case for the recursion.  
And if you correct that, it still doesn't work correctly for lists with 
repeated items.

How about:

def quicksort(L):
    if len(L) < 2: return L
    return quicksort([x for x in L if x < L[0]]) + \
           [x for x in L if x == L[0]] + \
           quicksort([x for x in L if x > L[0]])

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science