Fun with fancy slicing

[David Eppstein]

In article <7f9e1817.0310041817.4b5a8c23 at posting.google.com>,
 imcmeans at telus.net (Ian McMeans) wrote:

> def quicksort(lst): 
>      if len(lst) <= 1: return lst 
>       
>      left =   [x for x in lst if x <  lst[0]] 
>      middle = [x for x in lst if x == lst[0]] 
>      right =  [x for x in lst if x >  lst[0]] 
> 
>      return quicksort(left) + middle + quicksort(right)
> 
> >>> quicksort([random.randint(0, 20) for dummy in range(20)])
> [0, 1, 2, 4, 4, 4, 4, 4, 6, 6, 8, 9, 12, 12, 13, 14, 14, 14, 16, 16]
> 
> Hopefully this is still nlogn :)

Well, for random inputs it is.  If you want it to be O(n log n) even for 
sorted inputs you could change it a little:

def quicksort(lst): 
     if len(lst) <= 1: return lst 
     pivot = lst[random.randrange(len(lst))]
      
     left =   [x for x in lst if x <  pivot] 
     middle = [x for x in lst if x == pivot] 
     right =  [x for x in lst if x >  pivot] 

     return quicksort(left) + middle + quicksort(right)

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