>> Yeah, it just adds an extra traversal.
> 
>   The extra traversal can be used to perform the first partitioning
> (using eg. simply the first element as pivot), thus potentially reducing
> the overall amount of work.

Yeah, true. And that's the kind of trick Haskell's compiler is likely to 
pull off too...

>> (For a merge sort, you can split a list into the even and odd elements, 
>> sort, and then merge.
> 
>   But does this avoid creating new lists? In other words, can Haskell
> optimize it so that the merge sort is done in-place, without requiring
> any additional memory?

Well, between garbage collection, lazy evaluation and aggressive 
compiler optimisations, that's not a terribly easy question to answer.

Will it do it with absolutely *no* extra memory at all? Will it 
literally take a linked list in memory and just rewrite a few pointers 
to make it into a sorted list? I can more or less guarantee that's a "no".

Will it eat N log N extra memory? Again, I can more or less promise you 
that's a "no".

If the optimiser does what it's supposed to, and you're not holding on 
to a pointer to the original, unsorted list, it should allocate new list 
cells directly in sorted order, with GC cleaning up the old cells as the 
become unused. [I haven't studied the algorithm in detail, but I'm 
fairly confident the N log N potential intermediate lists can be elided 
by the optimiser.]

Of course, if sorting is just one part of a long pipeline of list 
operations, it's possible that the sorting could be partially merged 
with other steps in the pipeline too... as you once said, reasoning 
about Haskell program performance isn't that easy for the most part.

[The *other* possibility of course is to design your own brand new list 
type that supports explicit in-place updates. But if you're that worried 
about space efficiency, it'll probably be better to use an array...]

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

Post a reply to this message