Go rant

[Andrei Alexandrescu]

dsimcha wrote:
> == Quote from Walter Bright (newshound1 at digitalmars.com)'s article
>> qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
>> prominently featured in Haskell's official introduction page:
>> http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell
>> Ain't that cool? But look closer. The advantage of quicksort is that it
>> is an *in-place* sort. The Haskell one creates new arrays for every
>> state in the sort.
> 
> I think this can be optimized out in theory, though I have no idea how often it is
> in practice.
> 
>> The other fundamental problem with the Haskell
>> version is that it selects the first array element as the "pivot". This
>> is the worst choice, since arrays to be sorted tend to already be mostly
>> sorted, and quicksort gives quadratic performance to sort an already
>> sorted array with the first element as the pivot.
> 
> True.  All you'd need to remedy this, though, is a median of 3 function.

Median of N on singly-linked lists is highly nontrivial. More detail 
about the failings of functional qsort:

http://www.informit.com/articles/printerfriendly.aspx?p=1407357


Andrei