Orchid XP v7 <voi### [at] devnull> wrote:
> 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.

  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.

> (Interestingly, I don't think 
> that technically alters the complexity class of the algorithm...)

  No, because the "extra traversal" has to be done only once. That adds
only one 'n' to the total time, which does not affect the complexity class.

> >   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.

  Merge sort is quite efficient for linked lists because it can be done
in-place and without requiring extra memory. On the other hand, it's a bit
complicated to implement for linked lists.

> (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?

-- 
                                                          - Warp

Post a reply to this message