Fun with fancy slicing

[David Eppstein]

In article <xdJeb.208403$R32.6721730 at news2.tin.it>,
 Alex Martelli <aleax at aleax.it> wrote:

> David Eppstein wrote:
>    ...
> >> 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.
> 
> Right on both counts -- sorry.
> 
> > And if you correct that, it still doesn't work correctly for lists with
> > repeated items.
> 
> Why not?  Having fixed the syntax and added the base-case, I see:

Sorry, does work correctly, just not efficiently.  I didn't see the = in 
the first recursive call.  But if you call your quicksort on say [0]*n,
each call will split the list as unevenly as possible and you get 
quadratic runtime.  Of course we know that nonrandom quicksort pivoting 
can be quadratic anyway (e.g. on sorted input) but this to my mind is 
worse because randomization doesn't make it any better.  The fact that 
some textbooks  (e.g. CLRS!) make this mistake doesn't excuse it either.

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