Warp wrote:

>   As I have commented to you before, it is possible to use the median-of-3
> pivot choice even with linked lists.

Yeah, it just adds an extra traversal. (Interestingly, I don't think 
that technically alters the complexity class of the algorithm...)

>   Of course it's much easier to do with a true array, which I think it's
> one weak point of Haskell, at least currently?

Merge sort or heap sort is probably a more natural fit for Haskell.

(For a merge sort, you can split a list into the even and odd elements, 
sort, and then merge. Heapsort I've demonstrated here before...)

If you did want to do a quick sort, you'd have to decide whether you 
want to use immutable or mutable arrays. If I feel sufficiently bored 
I'll have a go at implementing them. (I'm curios to see what it would 
look like myself...)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message