[Haskell-cafe] will the real quicksort please stand up? (or: sorting a > million element list)

[Ketil Malde]

jerzy.karczmarczuk at info.unicaen.fr writes:

> 1. Avoid two pass filtering.
> 2. Avoid unecessary (++), with an accumulator. For example: 

Also, I find that 

  3. Accumulate equal elements, too

  pa (y:ys) s e b = case compare x y of ...

to be a good choice.  Otherwise, quicksort easily grows towards
quadratic if you have many multiples of the same value.  I think this
is more common than the other major pitfall, sorting an already sorted
list.  (But perhaps the three-way case based on 'compare' is more
expensive than the two-way (<) test?)

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants