Orchid XP v7 <voi### [at] devnull> wrote:
> Anyway, assuming you've already got a heapsort function that takes a 
> list and completely sorts it, and you want to swap from quicksort to 
> heapsort after exactly 16 iterations, you could do something like this:

  While introsort probably doesn't "officially" state how the pivot is
chosen, the median-of-3 choosing algorithm is the de-facto standard.

> Of course, a good quicksort utterly depends on picking the right pivot. 
> And for a linked list, it seems hard to do that without wasting too much 
> time trying to pick a pivot. So I'm not really sure quicksort is a good 
> algorithm to be using on a linked list in the first place, but hey...

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

  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?

-- 
                                                          - Warp

Post a reply to this message